Условие задачи
ДЖОИ-кун играет в раскраску, используя лист бумаги и малярный скотч.
Лист бумаги имеет прямоугольную форму, и на нём нарисована сетка из $H$ строк и $W$ столбцов. Клетка в $i$-й строке сверху ($1 \le i \le H$) и $j$-м столбце слева ($1 \le j \le W$) называется клеткой $(i, j)$.
Каждой клетке сопоставлен $1$ цвет. Цвета обозначаются целыми числами, и изначально цвет всех клеток равен $0$.
ДЖОИ-кун выполняет $Q$ операций, используя этот лист бумаги и малярный скотч. $k$-я операция ($1 \le k \le Q$) описывается следующим образом в зависимости от значения целого числа $q_k$:
- Если $q_k = 1$, эта операция задаётся целыми числами $x_k, y_k, c_k$. Для каждой из клеток $(x_k, y_k)$, $(x_k + 1, y_k)$, $(x_k, y_k + 1)$ и $(x_k + 1, y_k + 1)$, если клетка не заклеена малярным скотчем, цвет этой клетки меняется на $c_k$. Если клетка заклеена малярным скотчем, с ней ничего не происходит.
- Если $q_k = 2$, эта операция задаётся целыми числами $x_k, y_k$. Клетки $(x_k, y_k)$, $(x_k + 1, y_k)$, $(x_k, y_k + 1)$ и $(x_k + 1, y_k + 1)$ заклеиваются малярным скотчем.
После завершения всех $Q$ операций весь малярный скотч отклеивают. Обратите внимание, что когда с клетки отклеивают малярный скотч, её цвет становится таким же, каким он был непосредственно перед тем, как её заклеили малярным скотчем.
По данной информации о $Q$ операциях напишите программу, которая определит итоговые цвета всех клеток листа бумаги.
Ограничения
- $2 \le H \le 500$.
- $2 \le W \le 500$.
- $1 \le Q \le 200\,000$.
- $q_k$ равно либо $1$, либо $2$ ($1 \le k \le Q$).
- Если $q_k = 1$, то $1 \le x_k \le H - 1$, $1 \le y_k \le W - 1$, $1 \le c_k \le 10^9$ ($1 \le k \le Q$).
- Если $q_k = 2$, то $1 \le x_k \le H - 1$, $1 \le y_k \le W - 1$ ($1 \le k \le Q$).
- Все входные значения являются целыми числами.
Подзадачи
- ($32$ балла) $H = 2$, $W = 2$, $q_k = 1$ ($1 \le k \le Q$).
- ($32$ балла) $q_k = 1$ ($1 \le k \le Q$).
- ($36$ баллов) Дополнительных ограничений нет.
Входные данные
Входные данные даны в следующем формате:
$$ \begin{aligned} &H\ W\ Q \\ &(\text{Query } 1) \\ &(\text{Query } 2) \\ &\vdots \\ &(\text{Query } Q) \end{aligned} $$
Каждый запрос $(\text{Query } k)$ ($1 \le k \le Q$) содержит несколько целых чисел, разделённых пробелами. $1$-е целое число — это $q_k$, а содержимое этой строки имеет один из следующих видов:
- Если $q_k = 1$, далее в этой строке следуют $3$ целых числа $x_k, y_k, c_k$, разделённых пробелами.
- Если $q_k = 2$, далее в этой строке следуют $2$ целых числа $x_k, y_k$, разделённых пробелами.
Выходные данные
Выведите итоговые цвета всех клеток листа бумаги в $H$ строках. В $i$-й строке ($1 \le i \le H$) выведите $W$ целых чисел через пробел, где $j$-е число ($1 \le j \le W$) — цвет клетки $(i, j)$.
Примеры
Пример ввода 1
5 5 4 1 2 2 1 2 1 2 2 3 3 1 1 3 5
Пример вывода 1
0 0 0 5 0 0 1 1 5 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
Рассмотрим все $4$ операции по порядку.
Для $1$-й операции $q_1 = 1$. Так как клетки $(2, 2)$, $(2, 3)$, $(3, 2)$ и $(3, 3)$ не заклеены малярным скотчем, меняем их цвет на $1$.
В этот момент лист бумаги выглядит следующим образом:
0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
Для $2$-й операции $q_2 = 2$. Заклеиваем клетки $(1, 2)$, $(1, 3)$, $(2, 2)$ и $(2, 3)$ малярным скотчем.
В этот момент лист бумаги выглядит следующим образом. Отметим, что справа от числа, обозначающего цвет заклеенной малярным скотчем клетки, поставлен символ *:
0 0* 0* 0 0 0 1* 1* 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
Для $3$-й операции $q_3 = 2$. Заклеиваем клетки $(3, 3)$, $(3, 4)$, $(4, 3)$ и $(4, 4)$ малярным скотчем.
В этот момент лист бумаги выглядит следующим образом:
0 0* 0* 0 0 0 1* 1* 0 0 0 1 1* 0* 0 0 0 0* 0* 0 0 0 0 0 0
Для $4$-й операции $q_4 = 1$. Так как клетки $(1, 4)$ и $(2, 4)$ не заклеены малярным скотчем, меняем их цвет на $5$. Так как клетки $(1, 3)$ и $(2, 3)$ заклеены малярным скотчем, ничего с ними не делаем.
В этот момент лист бумаги выглядит следующим образом:
0 0* 0* 5 0 0 1* 1* 5 0 0 1 1* 0* 0 0 0 0* 0* 0 0 0 0 0 0
Таким образом, итоговые цвета всех клеток листа бумаги совпадают с приведёнными в примере вывода.
Этот пример удовлетворяет ограничениям подзадачи $3$.
Пример ввода 2
5 5 3 1 1 1 2 1 3 3 3 1 2 4 2
Пример вывода 2
2 2 0 0 0 2 2 0 2 2 0 0 3 2 2 0 0 3 3 0 0 0 0 0 0
Этот пример удовлетворяет ограничениям подзадач $2, 3$.
Пример ввода 3
10 10 10 2 5 7 2 5 6 1 5 6 1 1 9 2 1 2 1 1 1 2 4 2 2 3 2 1 2 2 3 1 9 9 2 1 8 8 1
Пример вывода 3
0 0 0 0 0 0 0 0 0 0 0 0 3 2 2 0 0 0 0 0 0 0 0 2 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 1 1 2 0 1 1 0 0 0 0 0 2 2
Этот пример удовлетворяет ограничениям подзадачи $3$.