题目背景

「笼中鸟，笼中鸟」

「笼中有只小小鸟」

「何时才能出囚笼」

「黎明时分的夜晚」

「仙鹤灵龟都滑倒」

「猜猜身后是何人」

题目描述

榎本在 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）