Умова задачі
ДЖОІ-кун грається у розмальовку, використовуючи аркуш паперу та малярний скотч.
Аркуш паперу має прямокутну форму, і на ньому намальовано сітку з $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$.