Verkefnalýsing
JOI-kun er að leika sér að lita með pappírsblaði og málningarteipi.
Pappírsblaðið er rétthyrnt og á það er teiknað hnitakerfi með $H$ röðum og $W$ dálkum. Reiturinn í $i$-tu röð að ofan ($1 \le i \le H$) og $j$-ta dálki frá vinstri ($1 \le j \le W$) kallast reitur $(i, j)$.
Hverjum reit er úthlutaður $1$ litur. Litir eru táknaðir með heiltölum og í upphafi er litur allra reita $0$.
JOI-kun framkvæmir $Q$ aðgerðir með þessu pappírsblaði og málningarteipi. $k$-ta aðgerðin ($1 \le k \le Q$) lýsir sér á eftirfarandi hátt eftir gildi heiltölunnar $q_k$:
- Þegar $q_k = 1$ er þessi aðgerð táknuð með heiltölunum $x_k, y_k, c_k$. Fyrir hvern reitanna $(x_k, y_k)$, $(x_k + 1, y_k)$, $(x_k, y_k + 1)$ og $(x_k + 1, y_k + 1)$, ef reiturinn er ekki hulinn málningarteipi, breyttu þá lit reitsins í $c_k$. Ef reiturinn er hulinn málningarteipi, gerðu þá ekkert við þann reit.
- Þegar $q_k = 2$ er þessi aðgerð táknuð með heiltölunum $x_k, y_k$. Hyljið reitina $(x_k, y_k)$, $(x_k + 1, y_k)$, $(x_k, y_k + 1)$ og $(x_k + 1, y_k + 1)$ með málningarteipi.
Eftir að öllum $Q$ aðgerðunum er lokið er allt málningarteipið tekið af. Athugið að þegar málningarteipið á reit er tekið af verður litur reitsins sá sami og hann var rétt áður en hann var hulinn með málningarteipi.
Með upplýsingum um $Q$ aðgerðirnar, skrifið forrit til að finna lokaliti allra reita á pappírsblaðinu.
Takmarkanir
- $2 \le H \le 500$.
- $2 \le W \le 500$.
- $1 \le Q \le 200\,000$.
- $q_k$ er annaðhvort $1$ eða $2$ ($1 \le k \le Q$).
- Þegar $q_k = 1$ gildir $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$).
- Þegar $q_k = 2$ gildir $1 \le x_k \le H - 1$, $1 \le y_k \le W - 1$ ($1 \le k \le Q$).
- Öll inntaksgildi eru heiltölur.
Undirverkefni
- ($32$ stig) $H = 2$, $W = 2$, $q_k = 1$ ($1 \le k \le Q$).
- ($32$ stig) $q_k = 1$ ($1 \le k \le Q$).
- ($36$ stig) Engar viðbótartakmarkanir.
Inntak
Inntakið er gefið á eftirfarandi sniði:
$$ \begin{aligned} &H\ W\ Q \\ &(\text{Query } 1) \\ &(\text{Query } 2) \\ &\vdots \\ &(\text{Query } Q) \end{aligned} $$
Hvert $(\text{Query } k)$ ($1 \le k \le Q$) inniheldur nokkrar heiltölur aðskildar með bilum. $1$. heiltalan er $q_k$ og innihald þessarar línu er annaðhvort eftirfarandi:
- Þegar $q_k = 1$ fylgja í þessari línu $3$ heiltölur aðskildar með bilum: $x_k, y_k, c_k$.
- Þegar $q_k = 2$ fylgja í þessari línu $2$ heiltölur aðskildar með bilum: $x_k, y_k$.
Úttak
Skrifið út lokaliti allra reita á pappírsblaðinu í $H$ línum. Á $i$-tu línu ($1 \le i \le H$), skrifið út $W$ heiltölur aðskildar með bilum, þar sem $j$-ta heiltalan ($1 \le j \le W$) er litur reits $(i, j)$.
Dæmi
Sýnidæmi (inntak) 1
5 5 4 1 2 2 1 2 1 2 2 3 3 1 1 3 5
Sýnidæmi (úttak) 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
Skoðum aðgerðirnar $4$ í röð.
Fyrir aðgerð $1$ er $q_1 = 1$. Þar sem reitirnir $(2, 2)$, $(2, 3)$, $(3, 2)$ og $(3, 3)$ eru allir óhuldir málningarteipi breytum við lit þeirra í $1$.
Á þessum tímapunkti lítur pappírsblaðið svona út:
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
Fyrir aðgerð $2$ er $q_2 = 2$. Hyljum reitina $(1, 2)$, $(1, 3)$, $(2, 2)$ og $(2, 3)$ með málningarteipi.
Á þessum tímapunkti lítur pappírsblaðið svona út. Athugið að * er bætt við hægra megin við heiltöluna sem táknar lit reits sem hulinn er málningarteipi:
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
Fyrir aðgerð $3$ er $q_3 = 2$. Hyljum reitina $(3, 3)$, $(3, 4)$, $(4, 3)$ og $(4, 4)$ með málningarteipi.
Á þessum tímapunkti lítur pappírsblaðið svona út:
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
Fyrir aðgerð $4$ er $q_4 = 1$. Þar sem reitirnir $(1, 4)$ og $(2, 4)$ eru ekki huldir málningarteipi breytum við lit þeirra í $5$. Þar sem reitirnir $(1, 3)$ og $(2, 3)$ eru huldir málningarteipi gerum við ekkert við þá.
Á þessum tímapunkti lítur pappírsblaðið svona út:
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
Því eru lokalitir allra reita á pappírsblaðinu eins og sýnt er í sýnidæminu.
Þetta dæmi uppfyllir takmarkanir undirverkefnis $3$.
Sýnidæmi (inntak) 2
5 5 3 1 1 1 2 1 3 3 3 1 2 4 2
Sýnidæmi (úttak) 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
Þetta dæmi uppfyllir takmarkanir undirverkefna $2, 3$.
Sýnidæmi (inntak) 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
Sýnidæmi (úttak) 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
Þetta dæmi uppfyllir takmarkanir undirverkefnis $3$.