G. 查询问题
时间限制：8 秒
内存限制：1024 MB

给定一个由 $n$ 个整数组成的数组 $a$。你的任务是处理 $q$ 个查询，查询有两种类型：

• 1 p x —— 将下标 $p$ 处的元素值设为 $x$；
• 2 l r —— 统计满足 $l \le i < j \le r$ 且 $a_i \neq a_j$ 的索引对 $(i, j)$ 的数量。

注意：本题中的查询是编码的；每个后续查询只有在计算出前一个第二类查询的答案后才能解码。

输入
第一行包含一个整数 $n$（$1 \le n \le 10^5$）。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）。
第三行包含一个整数 $q$（$1 \le q \le 3 \cdot 10^5$）—— 查询的数量。
接下来的 $q$ 行描述查询，格式为以下之一：

• 1 p' x'（$0 \le p', x' \le n-1$）；
• 2 l' r'（$0 \le l', r' \le n-1$）。

查询的编码方式如下：令 $last$ 为最新处理过的第二类查询的答案（初始 $last = 0$）。

• 若查询类型为 1，则$$p = ((p' + last) \bmod n) + 1$$ $$x = ((x' + last) \bmod n) + 1$$
• 若查询类型为 2，则$$l = ((l' + last) \bmod n) + 1$$ $$r = ((r' + last) \bmod n) + 1$$ 如果 $l > r$，则交换它们的值。

在处理完每个第二类查询后，记得更新 $last$ 的值。

输入附加约束：至少有一个第二类查询。

输出
对于每个第二类查询，输出答案 —— 满足 $l \le i < j \le r$ 且 $a_i \neq a_j$ 的索引对数量。

示例

输入：

3
1 2 3
5
2 0 2
1 0 2
2 0 2
1 2 0
2 1 0

输出：

3 2 0 

输入：

7
1 3 4 4 7 1 3
3
2 1 6
2 1 0
2 5 6

输出：

13 18 0 

说明
在第一个示例中，解码后的实际查询为：

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