Mystical Transfer Device Experiment

In this problem, Enomoto is experimenting with a mysterious transfer device in the SPHIA dark room. He uses \(m\) sequences, each of length \(n\), as his test subjects. The device can perform four types of operations on these sequences:

1. Given \(x, l, r\), compute \(\sum_{i=l}^{r} a_{x,i} \bmod p\).
2. Given \(x, l, r, f\), check whether for every \(i\) from \(l+f\) to \(r\) the condition \(a_{x,i} \equiv \sum_{j=1}^{f} a_{x,i-j} \pmod p\) holds.
3. Given \(x, l, r, k\), add \(k\) to each element \(a_{x,i}\) for \(i \in [l, r]\).
4. Given \(x, y, l, r\), swap the subarrays \(a_{x,l...r}\) and \(a_{y,l...r}\).

You are given \(m\) sequences initially. Then \(q\) operations are performed. For operations of type 1 and 2, you should output the answer as described. Note that all indices are 1-indexed.

inputFormat

The first line contains four integers: \(m\), \(n\), \(p\), and \(q\), where \(m\) is the number of sequences, \(n\) is the length of each sequence, \(p\) is the modulus, and \(q\) is the number of operations.

The next \(m\) lines each contain \(n\) integers representing the initial values of the sequences.

Then \(q\) lines follow, each describing an operation in one of the following formats:

• Type 1: 1 x l r
• Type 2: 2 x l r f
• Type 3: 3 x l r k
• Type 4: 4 x y l r

outputFormat

For each operation of type 1 or type 2, output the result on a separate line. For type 1, output the sum \(\sum_{i=l}^{r} a_{x,i} \bmod p\). For type 2, output 1 if the condition holds for every \(i \in [l+f, r]\) and 0 otherwise.

sample

2 5 100 4
1 2 3 4 5
5 4 3 2 1
1 1 5
2 2 3 5 2
3 1 2 4 10
1 1 5

15
0
45