Treść zadania
JOI-kun bawi się w kolorowanie za pomocą kartki papieru i taśmy malarskiej (maskującej).
Kartka papieru jest prostokątna i ma narysowaną siatkę o $H$ wierszach i $W$ kolumnach. Pole w $i$-tym wierszu od góry ($1 \le i \le H$) i $j$-tej kolumnie od lewej ($1 \le j \le W$) nazywamy polem $(i, j)$.
Każdemu polu przypisany jest $1$ kolor. Kolory są reprezentowane przez liczby całkowite, a początkowo kolor wszystkich pól wynosi $0$.
JOI-kun wykonuje $Q$ operacji przy użyciu tej kartki papieru i taśmy malarskiej. $k$-ta operacja ($1 \le k \le Q$) jest opisana następująco w zależności od wartości liczby całkowitej $q_k$:
- Gdy $q_k = 1$, operacja ta jest reprezentowana przez liczby całkowite $x_k, y_k, c_k$. Dla każdego z pól $(x_k, y_k)$, $(x_k + 1, y_k)$, $(x_k, y_k + 1)$ oraz $(x_k + 1, y_k + 1)$, jeśli pole nie jest zaklejone taśmą malarską, zmień kolor tego pola na $c_k$. Jeśli pole jest zaklejone taśmą malarską, nic z nim nie rób.
- Gdy $q_k = 2$, operacja ta jest reprezentowana przez liczby całkowite $x_k, y_k$. Zaklej pola $(x_k, y_k)$, $(x_k + 1, y_k)$, $(x_k, y_k + 1)$ oraz $(x_k + 1, y_k + 1)$ taśmą malarską.
Po zakończeniu wszystkich $Q$ operacji cała taśma malarska zostaje odklejona. Zauważ, że po odklejeniu taśmy malarskiej z danego pola jego kolor staje się taki sam, jaki był tuż przed zaklejeniem taśmą malarską.
Mając dane informacje o $Q$ operacjach, napisz program, który wyznaczy końcowe kolory wszystkich pól kartki papieru.
Ograniczenia
- $2 \le H \le 500$.
- $2 \le W \le 500$.
- $1 \le Q \le 200\,000$.
- $q_k$ wynosi $1$ lub $2$ ($1 \le k \le Q$).
- Gdy $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$).
- Gdy $q_k = 2$, $1 \le x_k \le H - 1$, $1 \le y_k \le W - 1$ ($1 \le k \le Q$).
- Wszystkie wartości wejściowe są liczbami całkowitymi.
Podzadania
- ($32$ punkty) $H = 2$, $W = 2$, $q_k = 1$ ($1 \le k \le Q$).
- ($32$ punkty) $q_k = 1$ ($1 \le k \le Q$).
- ($36$ punktów) Brak dodatkowych ograniczeń.
Wejście
Wejście podane jest w następującym formacie:
$$ \begin{aligned} &H\ W\ Q \\ &(\text{Query } 1) \\ &(\text{Query } 2) \\ &\vdots \\ &(\text{Query } Q) \end{aligned} $$
Każde $(\text{Query } k)$ ($1 \le k \le Q$) zawiera kilka liczb całkowitych oddzielonych spacjami. $1$-sza liczba całkowita to $q_k$, a zawartość tego wiersza jest jedną z poniższych:
- Gdy $q_k = 1$, w tym wierszu następują $3$ liczby całkowite $x_k, y_k, c_k$ oddzielone spacjami.
- Gdy $q_k = 2$, w tym wierszu następują $2$ liczby całkowite $x_k, y_k$ oddzielone spacjami.
Wyjście
Wypisz końcowe kolory wszystkich pól kartki papieru w $H$ wierszach. W $i$-tym wierszu ($1 \le i \le H$) wypisz $W$ liczb całkowitych oddzielonych spacjami, gdzie $j$-ta liczba całkowita ($1 \le j \le W$) oznacza kolor pola $(i, j)$.
Przykłady
Przykładowe wejście 1
5 5 4 1 2 2 1 2 1 2 2 3 3 1 1 3 5
Przykładowe wyjście 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
Prześledźmy kolejno $4$ operacje.
Dla $1$-szej operacji $q_1 = 1$. Ponieważ pola $(2, 2)$, $(2, 3)$, $(3, 2)$ oraz $(3, 3)$ nie są zaklejone taśmą malarską, zmieniamy ich kolor na $1$.
W tym momencie kartka papieru wygląda następująco:
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
Dla $2$-giej operacji $q_2 = 2$. Zaklejamy pola $(1, 2)$, $(1, 3)$, $(2, 2)$ oraz $(2, 3)$ taśmą malarską.
W tym momencie kartka papieru wygląda następująco. Zauważ, że po prawej stronie liczby oznaczającej kolor pola zaklejonego taśmą malarską dodano znak *:
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
Dla $3$-ciej operacji $q_3 = 2$. Zaklejamy pola $(3, 3)$, $(3, 4)$, $(4, 3)$ oraz $(4, 4)$ taśmą malarską.
W tym momencie kartka papieru wygląda następująco:
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
Dla $4$-tej operacji $q_4 = 1$. Ponieważ pola $(1, 4)$ oraz $(2, 4)$ nie są zaklejone taśmą malarską, zmieniamy ich kolor na $5$. Ponieważ pola $(1, 3)$ oraz $(2, 3)$ są zaklejone taśmą malarską, nic nie robimy.
W tym momencie kartka papieru wygląda następująco:
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
Zatem końcowe kolory wszystkich pól kartki papieru są takie, jak pokazano w przykładowym wyjściu.
Ten przykład spełnia ograniczenia podzadania $3$.
Przykładowe wejście 2
5 5 3 1 1 1 2 1 3 3 3 1 2 4 2
Przykładowe wyjście 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
Ten przykład spełnia ograniczenia podzadań $2, 3$.
Przykładowe wejście 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
Przykładowe wyjście 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
Ten przykład spełnia ograniczenia podzadania $3$.