暂无测试数据。

题目背景

\(\sf\pink{\sf FakzianQwQ }\) 住在
\(\sf\gray{KfZ}\)_\(\sf\gray{awa}\) 的对面。

但是他们在做数据结构题的时候打起来了。

于是这题只好由你来做了。

题目描述

给定一个从 \(1\) 到 \(n\) 的**排列** \(a\)，\(a\) 的下标从 \(1\) 开始，有 \(m\) 次操作。

定义：\(f(x)\) 代表 \(x\) 在 \(a\) 序列中的**下标**。

有三种操作：

1 x y：将 \(a_x\) 和 \(a_y\) 的位置**交换**。

2 l r：查询 \(\displaystyle\sum_{i=\min(f(l),f(r))}^{\max(f(l),f(r))}a_i\)。

3 l r：查询 \(\displaystyle\sum_{i=\min(a_l,a_r)}^{\max(a_l,a_r)}f(a_i)\)。

输入格式

第一行，两个数，代表 \(n\) 和 \(m\)。

第二行 \(n\) 个数，代表序列 \(a\)。

接下来 \(m\) 行，每行 \(3\) 个数，对应每次操作。

输出格式

对于每次询问。

输出一行，一个数，代表结果。

样例 #1

样例输入 #1

5 5 
5 3 2 1 4
1 3 4
2 1 4
3 4 4
2 1 2
3 1 5

样例输出 #1

7
4
3
6

提示

样例 1 解释：

操作 1 后，\(a\) 序列：\(5,3,1,2,4\)。

操作 2：\(f(1)=3,f(4)=5\)。

故结果等于 \(1+2+4=7\)。

操作 3：\(a_4=2\)。

故结果等于 \(f(2)=4\)。

本题采用捆绑测试。

数据范围：

| 子任务编号 |\(n\le\) |分值 |时限|

这是At赛制。

对于所有数据都有：\(1 \le m \le 10^5,1 \le l,r\le n\)。