Uppgift
JOI-kun leker en färgläggningslek med ett pappersark och maskeringstejp.
Pappersarket är rektangulärt och har ett rutnät med $H$ rader och $W$ kolumner ritat på sig. Rutan på den $i$-te raden uppifrån ($1 \le i \le H$) och den $j$-te kolumnen från vänster ($1 \le j \le W$) kallas ruta $(i, j)$.
Varje ruta har $1$ färg tilldelad. Färger representeras av heltal, och från början har alla rutor färgen $0$.
JOI-kun utför $Q$ operationer med detta pappersark och maskeringstejp. Den $k$-te operationen ($1 \le k \le Q$) beskrivs enligt följande beroende på värdet av heltalet $q_k$:
- När $q_k = 1$ representeras denna operation av heltalen $x_k, y_k, c_k$. För var och en av rutorna $(x_k, y_k)$, $(x_k + 1, y_k)$, $(x_k, y_k + 1)$ och $(x_k + 1, y_k + 1)$: om rutan inte är täckt med maskeringstejp, ändra färgen på den rutan till $c_k$. Om rutan är täckt med maskeringstejp, gör ingenting med den rutan.
- När $q_k = 2$ representeras denna operation av heltalen $x_k, y_k$. Täck rutorna $(x_k, y_k)$, $(x_k + 1, y_k)$, $(x_k, y_k + 1)$ och $(x_k + 1, y_k + 1)$ med maskeringstejp.
Efter att alla $Q$ operationer är klara dras all maskeringstejp bort. Observera att när maskeringstejpen på en ruta dras bort blir rutans färg densamma som den hade precis innan den täcktes med maskeringstejp.
Givet informationen om de $Q$ operationerna, skriv ett program som bestämmer de slutliga färgerna på alla rutor på pappersarket.
Begränsningar
- $2 \le H \le 500$.
- $2 \le W \le 500$.
- $1 \le Q \le 200\,000$.
- $q_k$ är antingen $1$ eller $2$ ($1 \le k \le Q$).
- När $q_k = 1$ gäller $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$).
- När $q_k = 2$ gäller $1 \le x_k \le H - 1$, $1 \le y_k \le W - 1$ ($1 \le k \le Q$).
- Alla indatavärden är heltal.
Deluppgifter
- ($32$ poäng) $H = 2$, $W = 2$, $q_k = 1$ ($1 \le k \le Q$).
- ($32$ poäng) $q_k = 1$ ($1 \le k \le Q$).
- ($36$ poäng) Inga ytterligare begränsningar.
Indata
Indata ges i följande format:
$$ \begin{aligned} &H\ W\ Q \\ &(\text{Query } 1) \\ &(\text{Query } 2) \\ &\vdots \\ &(\text{Query } Q) \end{aligned} $$
Varje $(\text{Query } k)$ ($1 \le k \le Q$) innehåller flera mellanslagsseparerade heltal. Det $1$-a heltalet är $q_k$, och innehållet på denna rad är ett av följande:
- När $q_k = 1$ följs denna rad av $3$ mellanslagsseparerade heltal $x_k, y_k, c_k$.
- När $q_k = 2$ följs denna rad av $2$ mellanslagsseparerade heltal $x_k, y_k$.
Utdata
Skriv ut de slutliga färgerna på alla rutor på pappersarket på $H$ rader. På den $i$-te raden ($1 \le i \le H$), skriv ut $W$ mellanslagsseparerade heltal, där det $j$-te heltalet ($1 \le j \le W$) är färgen på ruta $(i, j)$.
Exempel
Exempelindata 1
5 5 4 1 2 2 1 2 1 2 2 3 3 1 1 3 5
Exempelutdata 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
Låt oss undersöka de $4$ operationerna i ordning.
För den $1$-a operationen är $q_1 = 1$. Eftersom rutorna $(2, 2)$, $(2, 3)$, $(3, 2)$ och $(3, 3)$ inte är täckta med maskeringstejp ändras deras färg till $1$.
Vid detta tillfälle ser pappersarket ut så här:
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
För den $2$-a operationen är $q_2 = 2$. Täck rutorna $(1, 2)$, $(1, 3)$, $(2, 2)$ och $(2, 3)$ med maskeringstejp.
Vid detta tillfälle ser pappersarket ut så här. Observera att * har lagts till till höger om heltalet som representerar färgen på en ruta täckt med maskeringstejp:
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
För den $3$-e operationen är $q_3 = 2$. Täck rutorna $(3, 3)$, $(3, 4)$, $(4, 3)$ och $(4, 4)$ med maskeringstejp.
Vid detta tillfälle ser pappersarket ut så här:
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
För den $4$-e operationen är $q_4 = 1$. Eftersom rutorna $(1, 4)$ och $(2, 4)$ inte är täckta med maskeringstejp ändras deras färg till $5$. Eftersom rutorna $(1, 3)$ och $(2, 3)$ är täckta med maskeringstejp görs ingenting.
Vid detta tillfälle ser pappersarket ut så här:
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
Därför blir de slutliga färgerna på alla rutor på pappersarket som i exempelutdata.
Detta exempel uppfyller begränsningarna för deluppgift $3$.
Exempelindata 2
5 5 3 1 1 1 2 1 3 3 3 1 2 4 2
Exempelutdata 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
Detta exempel uppfyller begränsningarna för deluppgifterna $2, 3$.
Exempelindata 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
Exempelutdata 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
Detta exempel uppfyller begränsningarna för deluppgift $3$.