Я ненавижу слово «судьба». Рождение, встречи, расставания. Успехи и неудачи, удача и несчастья в жизни. Если всё это предопределено судьбой заранее, То для чего мы тогда рождаемся? Те, кто родился в богатой семье, Те, кого родила красивая мать, Те, кто родился во времена голода и войны. Если всё это — судьба, То боги слишком неразумны и жестоки. С тех пор у нас нет будущего, Потому что мы глубоко осознаем, что нам суждено ничего не добиться. «Пингвиний барабан»

Дан матричный массив $n\times m$, в котором номера строк возрастают сверху вниз, а номера столбцов — слева направо. Необходимо выполнить $q$ операций:

1. Даны $x_1, y_1, x_2, y_2, v$. Прибавить $v$ ко всем элементам в прямоугольной области $x_1\le x\le x_2, y_1\le y\le y_2$.
2. Даны $x_1, y_1, l, t$. Повернуть квадратную область с верхним левым углом $(x_1, y_1)$ и размером $(l+1)\times (l+1)$ против часовой стрелки на $t\times 90^\circ$.

В одном из тестов встречается случай $opt=0$, его следует обрабатывать как $opt=2$.

Выведите матрицу после выполнения всех операций.

Все числа в матрице вычисляются по модулю $2^{32}$, что позволяет использовать тип unsigned int для вычислений.

Входные данные

В первой строке содержатся четыре числа $n, m, q, \mathrm{lim}$.

Далее следуют $q$ строк, каждая из которых начинается с числа $opt$, обозначающего тип операции, за которым следуют соответствующие параметры.

Выходные данные

Чтобы уменьшить объем вывода, выведите $\mathrm{lim}$ чисел.

Пусть элемент матрицы в $i$-й строке и $j$-м столбце равен a[i][j]. Определим:

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

Выведите значения output[0], output[1], ... output[lim - 1].

Примеры

Пример 1

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

Выходные данные 1

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

Объяснение 1

Первая операция:

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

Вторая операция:

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

Ограничения

Для $100\%$ данных гарантируется $1\le n, m, q\le 2,000, \mathrm{lim} = \min(nm, 10^5)$.

Пустые ячейки означают отсутствие дополнительных ограничений.

Примечание

Это задача на базовые структуры данных.