Background

"Caged bird, caged bird"

"There is a tiny bird in the cage"

"When can it escape the prison cage"

"Night at dawn"

"Even the crane and the spirit turtle slip"

"Guess who is behind you"

Problem Description

Enomoto is experimenting with a mysterious transfer device in SPHIA’s small dark room.

There are $m$ sequences of length $n$. He wants to verify whether the transfer device can run correctly on these sequences.

The main function of this device is to swap parts of two sequences. That is, it will choose $(i,j),[l,r]$, and then swap the segment $[l,r]$ of sequence $i$ with the segment $[l,r]$ of sequence $j$.

Of course, to verify whether the swap is successful, he will query whether the sum of some interval of a sequence matches the expected value. Also, to avoid randomness, he will add a value to some interval of a sequence.

Enomoto knows that self likes the Fibonacci sequence very much, so to better trap self, he added another function: to determine whether an interval of a sequence $f$ is a special sequence satisfying $f_i\equiv\sum_{j=1}^kf_{i-j}\pmod p$.

Formal statement:

1. Given $x,l,r$, compute $\sum_{i=l}^r a_{x,i}\bmod p$.

2. Given $x,l,r,f$, ask whether the proposition $\forall i\in[l+f,r],a_{x,i}\equiv \sum_{j=1}^f a_{x,i-j}\pmod p$ is true.

3. Given $x,l,r,k$, $\forall i\in[l,r],a_{x,i}← a_{x,i}+k$.

4. Given $x,y,l,r$, $\forall i\in[l,r],\text{swap}(a_{x,i},a_{y,i})$.

Input Format

The first line contains four positive integers $n,m,q,p$, where $q$ is the number of operations.

The next $m$ lines each contain $n$ integers. The $j$-th number in the $i$-th line represents $a_{i,j}$.

The next $q$ lines each contain four or five integers.

If the input is 1 x l r, it means performing operation $1$ on interval $[l,r]$. If the input is 2 x l r f, it means performing operation $2$ on interval $[l,r]$. If the input is 3 x l r k, it means performing operation $3$ on interval $[l,r]$. If the input is 4 x y l r, it means performing operation $4$ on interval $[l,r]$.

Output Format

For each operation $1$, output one positive integer per line as the answer.

For each operation $2$, if the proposition is true output where is self?, otherwise output 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

Hint

"This problem uses bundled testcases."

$\texttt{Subtask 1(20pts):}n,q\le100$.

$\texttt{Subtask 2(25pts):}n,q\le10^5$.

$\texttt{Subtask 3(25pts):}$ there is no operation $2$.

$\texttt{Subtask 4(30pts):}$ no special properties.

For all testdata, $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$. It is guaranteed that $p$ is a randomly generated prime between $10^{9}$ and $2\times 10^9$.

After the contest on 2024/2/13, two sets of hack data (Subtask #5) were added.

Translated by ChatGPT 5