Tehtävänanto
JOI-kun leikkii väritysleikkiä käyttäen paperiarkkia ja maalarinteippiä.
Paperiarkki on suorakulmainen, ja siihen on piirretty $H$ rivin ja $W$ sarakkeen ruudukko. Ylhäältä lukien $i$-nnellä rivillä ($1 \le i \le H$) ja vasemmalta lukien $j$-nnessä sarakkeessa ($1 \le j \le W$) olevaa ruutua kutsutaan ruuduksi $(i, j)$.
Jokaiselle ruudulle on määritetty $1$ väri. Värit esitetään kokonaislukuina, ja aluksi kaikkien ruutujen väri on $0$.
JOI-kun suorittaa $Q$ operaatiota käyttäen tätä paperiarkkia ja maalarinteippiä. $k$-s operaatio ($1 \le k \le Q$) määritellään kokonaisluvun $q_k$ arvon perusteella seuraavasti:
- Kun $q_k = 1$, tätä operaatiota kuvaavat kokonaisluvut $x_k, y_k, c_k$. Jokaiselle ruuduista $(x_k, y_k)$, $(x_k + 1, y_k)$, $(x_k, y_k + 1)$ ja $(x_k + 1, y_k + 1)$: jos ruutua ei ole peitetty maalarinteipillä, vaihda kyseisen ruudun väriksi $c_k$. Jos ruutu on peitetty maalarinteipillä, älä tee sille mitään.
- Kun $q_k = 2$, tätä operaatiota kuvaavat kokonaisluvut $x_k, y_k$. Peitä ruudut $(x_k, y_k)$, $(x_k + 1, y_k)$, $(x_k, y_k + 1)$ ja $(x_k + 1, y_k + 1)$ maalarinteipillä.
Kun kaikki $Q$ operaatiota on suoritettu, kaikki maalarinteipit irrotetaan. Huomaa, että kun ruudussa oleva maalarinteippi irrotetaan, ruudun väriksi tulee sama väri, joka sillä oli juuri ennen kuin se peitettiin maalarinteipillä.
Kun $Q$ operaation tiedot on annettu, kirjoita ohjelma, joka selvittää paperiarkin kaikkien ruutujen lopulliset värit.
Rajoitukset
- $2 \le H \le 500$.
- $2 \le W \le 500$.
- $1 \le Q \le 200\,000$.
- $q_k$ on joko $1$ tai $2$ ($1 \le k \le Q$).
- Kun $q_k = 1$, pätee $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$).
- Kun $q_k = 2$, pätee $1 \le x_k \le H - 1$, $1 \le y_k \le W - 1$ ($1 \le k \le Q$).
- Kaikki syötteen arvot ovat kokonaislukuja.
Osatehtävät
- ($32$ pistettä) $H = 2$, $W = 2$, $q_k = 1$ ($1 \le k \le Q$).
- ($32$ pistettä) $q_k = 1$ ($1 \le k \le Q$).
- ($36$ pistettä) Ei lisärajoituksia.
Syöte
Syöte annetaan seuraavassa muodossa:
$$ \begin{aligned} &H\ W\ Q \\ &(\text{Query } 1) \\ &(\text{Query } 2) \\ &\vdots \\ &(\text{Query } Q) \end{aligned} $$
Jokainen $(\text{Query } k)$ ($1 \le k \le Q$) sisältää useita välilyönnein erotettuja kokonaislukuja. $1$. kokonaisluku on $q_k$, ja tämän rivin sisältö on jompikumpi seuraavista:
- Kun $q_k = 1$, tällä rivillä seuraa $3$ välilyönnein erotettua kokonaislukua $x_k, y_k, c_k$.
- Kun $q_k = 2$, tällä rivillä seuraa $2$ välilyönnein erotettua kokonaislukua $x_k, y_k$.
Tuloste
Tulosta paperiarkin kaikkien ruutujen lopulliset värit $H$ rivillä. Tulosta $i$-nnellä rivillä ($1 \le i \le H$) $W$ välilyönnein erotettua kokonaislukua, missä $j$-s kokonaisluku ($1 \le j \le W$) on ruudun $(i, j)$ väri.
Esimerkit
Esimerkkisyöte 1
5 5 4 1 2 2 1 2 1 2 2 3 3 1 1 3 5
Esimerkkituloste 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
Tarkastellaan $4$ operaatiota järjestyksessä.
Operaatiossa $1$ pätee $q_1 = 1$. Koska ruutuja $(2, 2)$, $(2, 3)$, $(3, 2)$ ja $(3, 3)$ ei ole peitetty maalarinteipillä, niiden väriksi vaihdetaan $1$.
Tällöin paperiarkki näyttää seuraavalta:
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
Operaatiossa $2$ pätee $q_2 = 2$. Peitetään ruudut $(1, 2)$, $(1, 3)$, $(2, 2)$ ja $(2, 3)$ maalarinteipillä.
Tällöin paperiarkki näyttää seuraavalta. Huomaa, että maalarinteipillä peitetyn ruudun väriä esittävän kokonaisluvun oikealle puolelle on lisätty *:
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
Operaatiossa $3$ pätee $q_3 = 2$. Peitetään ruudut $(3, 3)$, $(3, 4)$, $(4, 3)$ ja $(4, 4)$ maalarinteipillä.
Tällöin paperiarkki näyttää seuraavalta:
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
Operaatiossa $4$ pätee $q_4 = 1$. Koska ruutuja $(1, 4)$ ja $(2, 4)$ ei ole peitetty maalarinteipillä, niiden väriksi vaihdetaan $5$. Koska ruudut $(1, 3)$ ja $(2, 3)$ on peitetty maalarinteipillä, niille ei tehdä mitään.
Tällöin paperiarkki näyttää seuraavalta:
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
Näin ollen paperiarkin kaikkien ruutujen lopulliset värit ovat esimerkkitulosteen mukaiset.
Tämä esimerkki täyttää osatehtävän $3$ rajoitukset.
Esimerkkisyöte 2
5 5 3 1 1 1 2 1 3 3 3 1 2 4 2
Esimerkkituloste 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
Tämä esimerkki täyttää osatehtävien $2, 3$ rajoitukset.
Esimerkkisyöte 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
Esimerkkituloste 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
Tämä esimerkki täyttää osatehtävän $3$ rajoitukset.