seuOJ531 - Swap, Splice and Modulus

题目类型：传统
输入文件：标准输入流
输出文件：标准输出流
时间限制：2000 ms
空间限制：1024 MiB
题目标签：Div.1, 2025

题目描述

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

输出样例