Oppgave
JOI-kun leker en fargeleggingslek med et papirark og maskeringsteip.
Papirarket er rektangulært og har et rutenett med $H$ rader og $W$ kolonner tegnet på seg. Ruten i den $i$-te raden ovenfra ($1 \le i \le H$) og den $j$-te kolonnen fra venstre ($1 \le j \le W$) kalles rute $(i, j)$.
Hver rute er tildelt $1$ farge. Farger representeres av heltall, og til å begynne med er fargen på alle rutene $0$.
JOI-kun utfører $Q$ operasjoner med dette papirarket og maskeringsteip. Den $k$-te operasjonen ($1 \le k \le Q$) beskrives som følger avhengig av verdien til heltallet $q_k$:
- Når $q_k = 1$, representeres denne operasjonen av heltallene $x_k, y_k, c_k$. For hver av rutene $(x_k, y_k)$, $(x_k + 1, y_k)$, $(x_k, y_k + 1)$ og $(x_k + 1, y_k + 1)$: hvis ruten ikke er dekket med maskeringsteip, endres fargen på ruten til $c_k$. Hvis ruten er dekket med maskeringsteip, gjøres ingenting med den ruten.
- Når $q_k = 2$, representeres denne operasjonen av heltallene $x_k, y_k$. Dekk rutene $(x_k, y_k)$, $(x_k + 1, y_k)$, $(x_k, y_k + 1)$ og $(x_k + 1, y_k + 1)$ med maskeringsteip.
Etter at alle de $Q$ operasjonene er ferdige, rives all maskeringsteipen av. Merk at når maskeringsteipen på en rute rives av, blir fargen på ruten den samme som den var rett før den ble dekket med maskeringsteip.
Gitt informasjonen om de $Q$ operasjonene, skriv et program som finner de endelige fargene på alle rutene på papirarket.
Begrensninger
- $2 \le H \le 500$.
- $2 \le W \le 500$.
- $1 \le Q \le 200\,000$.
- $q_k$ er enten $1$ eller $2$ ($1 \le k \le Q$).
- Når $q_k = 1$, gjelder $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$, gjelder $1 \le x_k \le H - 1$, $1 \le y_k \le W - 1$ ($1 \le k \le Q$).
- Alle inndataverdier er heltall.
Deloppgaver
- ($32$ poeng) $H = 2$, $W = 2$, $q_k = 1$ ($1 \le k \le Q$).
- ($32$ poeng) $q_k = 1$ ($1 \le k \le Q$).
- ($36$ poeng) Ingen ytterligere begrensninger.
Inndata
Inndataene gis i følgende format:
$$ \begin{aligned} &H\ W\ Q \\ &(\text{Query } 1) \\ &(\text{Query } 2) \\ &\vdots \\ &(\text{Query } Q) \end{aligned} $$
Hver $(\text{Query } k)$ ($1 \le k \le Q$) inneholder flere mellomromseparerte heltall. Det $1$-ste heltallet er $q_k$, og innholdet på denne linjen er ett av følgende:
- Når $q_k = 1$, etterfølges denne linjen av $3$ mellomromseparerte heltall $x_k, y_k, c_k$.
- Når $q_k = 2$, etterfølges denne linjen av $2$ mellomromseparerte heltall $x_k, y_k$.
Utdata
Skriv ut de endelige fargene på alle rutene på papirarket på $H$ linjer. På den $i$-te linjen ($1 \le i \le H$) skal du skrive ut $W$ mellomromseparerte heltall, der det $j$-te heltallet ($1 \le j \le W$) er fargen på rute $(i, j)$.
Eksempler
Eksempelinndata 1
5 5 4 1 2 2 1 2 1 2 2 3 3 1 1 3 5
Eksempelutdata 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
La oss se på de $4$ operasjonene i rekkefølge.
For den $1$-ste operasjonen er $q_1 = 1$. Siden rutene $(2, 2)$, $(2, 3)$, $(3, 2)$ og $(3, 3)$ ikke er dekket med maskeringsteip, endres fargen deres til $1$.
På dette tidspunktet ser papirarket slik ut:
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
For den $2$-dre operasjonen er $q_2 = 2$. Dekk rutene $(1, 2)$, $(1, 3)$, $(2, 2)$ og $(2, 3)$ med maskeringsteip.
På dette tidspunktet ser papirarket slik ut. Merk at * er lagt til til høyre for heltallet som representerer fargen på en rute dekket med maskeringsteip:
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
For den $3$-dje operasjonen er $q_3 = 2$. Dekk rutene $(3, 3)$, $(3, 4)$, $(4, 3)$ og $(4, 4)$ med maskeringsteip.
På dette tidspunktet ser papirarket slik ut:
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
For den $4$-de operasjonen er $q_4 = 1$. Siden rutene $(1, 4)$ og $(2, 4)$ ikke er dekket med maskeringsteip, endres fargen deres til $5$. Siden rutene $(1, 3)$ og $(2, 3)$ er dekket med maskeringsteip, gjøres ingenting.
På dette tidspunktet ser papirarket slik ut:
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
Derfor blir de endelige fargene på alle rutene på papirarket som vist i eksempelutdataene.
Dette eksempelet oppfyller begrensningene i deloppgave $3$.
Eksempelinndata 2
5 5 3 1 1 1 2 1 3 3 3 1 2 4 2
Eksempelutdata 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
Dette eksempelet oppfyller begrensningene i deloppgave $2, 3$.
Eksempelinndata 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
Eksempelutdata 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
Dette eksempelet oppfyller begrensningene i deloppgave $3$.