J. Swap, Splice and Modulus

给你一个以长度 $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$。

第一行，一个整数 $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$。

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

输入样例

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

输出样例

12341
13
644986728
141911165
47833121