I hate the word "fate." Birth, encounters, partings, Success and failure, fortune and misfortune in life. If all of these are predetermined by fate, Then why were we even born? Those born into wealthy families, Those born to beautiful mothers, Those born during times of famine and war. If all of this is fate, Then God is too unreasonable, too cruel. From that moment on, we had no future, Because we knew deep down that we would never amount to anything. — Mawaru Penguindrum

You are given an $n \times m$ matrix where row indices increase from top to bottom and column indices increase from left to right. Perform $q$ operations on it:

1. Given $x_1, y_1, x_2, y_2, v$, add $v$ to all elements in the subgrid defined by $x_1 \le x \le x_2$ and $y_1 \le y \le y_2$.
2. Given $x_1, y_1, l, t$, rotate the square subgrid defined by $x_1 \le x \le x_1 + l$ and $y_1 \le y \le y_1 + l$ counter-clockwise by $t \times 90^\circ$.

Note: One of the test cases contains $opt=0$, please treat it as $opt=2$.

Output the matrix after all operations are completed.

All numbers in the matrix are taken modulo $2^{32}$, which means you can use unsigned int for calculations.

Input

The first line contains four integers $n, m, q, \mathrm{lim}$.

The next $q$ lines each start with an integer $opt$ representing the operation type, followed by the corresponding parameters for that operation.

Output

To reduce the amount of output, output $\mathrm{lim}$ numbers.

Let $a[i][j]$ be the value at the $i$-th row and $j$-th column of the matrix. Define:

output[((i - 1) * m + j - 1) % lim] ^= a[i][j] + ((i - 1) * m + j - 1) / lim

Output the array output[0], output[1], ... output[lim - 1].

Examples

Input 1

4 4 2 16
1 2 2 4 4 1
2 3 1 1 1

Output 1

0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 1

Note

First operation:

0 0 0 0
0 1 1 1
0 1 1 1
0 1 1 1

Second operation:

0 0 0 0
0 1 1 1
1 1 1 1
0 0 1 1

Constraints

For $100\%$ of the data, $1 \le n, m, q \le 2,000$, $\mathrm{lim} = \min(nm, 10^5)$.

Empty cells indicate no additional constraints.

Note

This is a basic data structure problem.