[LSOT-2] 笼中鸟

> 「笼中鸟，笼中鸟」 > > 「笼中有只小小鸟」 > > 「何时才能出囚笼」 > > 「黎明时分的夜晚」 > > 「仙鹤灵龟都滑倒」 > > 「猜猜身后是何人」

榎本在 SPHIA 的小黑屋内实验神秘转移装置。 实验体是 $m$ 个长度为 $n$ 的数列，他要在这些数列上验证转移装置是否能够正常运行。 这个转移装置的主要功能是将两个序列的部分交换，也就是说他会选择 $(i,j),[l,r]$，然后将序列 $i$ 的 $[l,r]$ 与序列 $j$ 的 $[l,r]$ 交换。 当然了，为了验证是否成功交换，他会查询某个序列的某个区间的和与预期值是否相同，并且为了避免偶然现象，他会给某个序列的某个区间加上一个值。 榎本知道 self 非常喜欢斐波那契数列，于是为了更好的困住 self，他还加了一个功能，就是判断数列 $f$ 的某个区间是不是满足 $f_i\equiv\sum_{j=1}^kf_{i-j}\pmod p$ 的特殊数列。 形式化题面： 1. 给定 $x,l,r$，求 $\sum_{i=l}^ra_{x,i}\bmod p$。 2. 给定 $x,l,r,f$，询问命题 $\forall i\in[l+f,r],a_{x,i}\equiv \sum_{j=1}^fa_{x,i-j}\pmod p$ 是否是真命题。 3. 给定 $x,l,r,k$，$\forall i\in[l,r],a_{x,i}← a_{x,i}+k$。 4. 给定 $x,y,l,r$，$\forall i\in[l,r],\text{swap}(a_{x,i},a_{y,i})$。

第一行四个正整数 $n,m,q,p$，$q$ 代表榎本的操作数。 接下来 $m$ 行每行 $n$ 个整数，第 $i$ 行的第 $j$ 个数代表 $a_{i,j}$。 接下来 $q$ 行，每行四个或五个整数。 若输入为 `1 x l r` 则代表对区间 $[l,r]$ 进行一次 $1$ 操作，若输入为 `2 x l r f` 则代表对区间 $[l,r]$ 进行一次 $2$ 操作，若输入为 `3 x l r k` 则代表对区间 $[l,r]$ 进行一次 $3$ 操作，若输入为 `4 x y l r ` 则代表对区间 $[l,r]$ 进行一次 $4$ 操作。

对于每个 $1$ 操作，一行一个正整数表示答案。 对于每个 $2$ 操作，如果是真命题输出 `where is self?`，否则输出 `infinity loop!`。

5 2 6 1000000007
1 1 2 3 5
0 0 0 0 0
1 1 2 3
1 2 2 3
2 1 1 5 2
4 1 2 2 3
1 1 1 4
1 2 1 4

3
0
where is self?
4
3

**「本题采用捆绑测试」** $\texttt{Subtask 1(20pts)：}n,q\le100$。 $\texttt{Subtask 2(25pts)：}n,q\le10^5$。 $\texttt{Subtask 3(25pts)：}$不存在 $2$ 操作。 $\texttt{Subtask 4(30pts)：}$无特殊性质。 对于所有数据，$1\le n,q\le5\times10^5$，$1\le m\le10$，$0\le a_{i,j},k< p$，$1\le l\le r\le n$，$1\le f\le n$，$1\le x,y\le m$，$x\not=y$。保证 $p$ 是 $10^{9}$ 到 $2\times 10^9$ 中随机生成的质数。 ------------ 2024/2/13 本题赛后添加两组 hack 数据（Subtask #5）