J. Swap, Splice and Modulus
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

给你一个以长度 $$$n$$$ 为循环周期的无限长度的正整数序列 $$$a_1,a_2\dots$$$ 和一个质数 $$$p$$$。不仅如此，还有对这个无限长度的序列的如下两种操作：

  • $$$1$$$ $$$i$$$ $$$j$$$：对于所有的 $$$k\in N$$$，交换序列中所有的 $$$a_{k\times n+i}$$$ 和 $$$a_{k\times n +j}$$$。
  • $$$2$$$ $$$x$$$：求出这个无限长度的循环序列的前 $$$x$$$ 个数拼接$$$^{\dagger}$$$在一起后对于 $$$p$$$ 取模的结果。

$$$^{\dagger}$$$对于两个正整数来说，将这两个数字$$$\it{拼接}$$$在一起意味着把这两个数字像字符串一样从左向右连接到一起，从而得到一个新的正整数。举个例子，将 $$$123$$$ 和 $$$45$$$ 拼接在一起的结果为 $$$12345$$$。

Input

第一行，一个整数 $$$t(1\le t\le 10^4)$$$，代表数据组数。

对于每组数据：

第一行，三个整数 $$$n,q,p(1\le n \le 3·10^5;1\le q \le 3·10^5;10^9-10^7\le p\le 10^9+10^7)$$$，分别代表无限序列的循环周期，询问的次数和操作二的模数，保证 $$$p$$$ 是一个质数。

第二个，$$$n$$$ 个整数 $$$a_1,\dots,a_n(1\le a_i\le 10^9)$$$，代表无限循环序列的前 $$$n$$$ 个数字。

接下来连续的 $$$q$$$ 行，每行现有一个整数 $$$op(1\le op\le2)$$$，代表操作的类型。如果 $$$op=1$$$，那么接下来有两个整数 $$$i,j(1\le i,j\le n)$$$，代表交换无限循环序列的前 $$$n$$$ 个数字中的 $$$a_i$$$ 和 $$$a_j$$$（后面所有周期中的数字也会被交换）。如果 $$$op=2$$$，那么接下来仅有一个数字 $$$x(1\le x \le 2·10^9)$$$，代表询问将无限循环序列的前 $$$x$$$ 个数字拼接在一起后对于 $$$p$$$ 取模的结果是多少。

保证对于每组数据，第一个询问的操作类型 $$$op=2$$$。

保证同一测试点内 $$$n$$$ 和 $$$q$$$ 的和均不会超过 $$$3·10^5$$$。

Output

对于每个操作类型 $$$op=2$$$ 的询问，输出一行整数代表答案。

Example
Input
2
4 4 998244353
1 2 3 4
2 5
1 2 3
2 2
2 12
6 5 1000000007
1 145 14 19 19 180
2 6
1 1 3
1 5 6
1 2 2
2 916619
Output
12341
13
644986728
141911165
47833121