给定一个长度为 $N$ 的序列 $A_1, A_2, \ldots, A_N$。请编写一个程序执行以下查询：

• 1 l r：令 $S$ 为从第 $l$ 个数到第 $r$ 个数构成的排序后的集合，输出以下值：[\left(\sum_{1 \le i < j < k \le |S|}{S_iS_jS_k}\right) \mod{10^9+7}]
• 2 x y：令 $A_x = y$
• 3 x：删除第 $x$ 个数
• 4 z y：在第 $z$ 个位置之后插入 $y$。如果 $z = 0$，则在最前面插入 $y$。
• 5 l r：输出第 $l$ 个数到第 $r$ 个数中不同数的个数。

序列的索引从 $1$ 开始，序列的大小始终大于或等于 $1$。

输入格式

第一行包含一个整数 $N$，表示序列的长度。

第二行包含 $A_1, A_2, \ldots, A_N$。

第三行包含一个整数 $M$，表示查询的个数。

接下来 $M$ 行，每行一个查询。

• $1 \le N, M \le 100{,}000$
• $1 \le A_i, y \le 10^9+6$
• $1 \le x \le |A|$
• $1 \le l \le r \le |A|$
• $0 \le z \le |A|$

输出格式

对于类型 1 和类型 5 的查询，按顺序每行输出一个答案。

样例

样例输入 1

5
1 2 3 2 1
8
1 1 3
5 1 5
2 2 4
1 2 4
3 3
4 0 5
1 1 2
1 1 5

样例输出 1

6
3
24
0
78

样例输入 2

10
5 4 3 5 4 1 5 4 3 1
15
2 8 580347
4 6 503576
1 2 5
5 8 11
1 2 6
4 7 565239
3 6
3 11
3 3
2 9 674360
1 1 6
2 2 589693
4 5 236488
1 8 9
5 2 7

样例输出 2

60
4
107
788510349
0
6