Testo del problema
JOI-kun sta giocando a colorare usando un foglio di carta e del nastro di mascheratura (masking tape).
Il foglio di carta è rettangolare e su di esso è disegnata una griglia di $H$ righe e $W$ colonne. La cella nella $i$-esima riga dall'alto ($1 \le i \le H$) e nella $j$-esima colonna da sinistra ($1 \le j \le W$) è chiamata cella $(i, j)$.
A ciascuna cella è assegnato $1$ colore. I colori sono rappresentati da numeri interi e inizialmente il colore di tutte le celle è $0$.
JOI-kun esegue $Q$ operazioni utilizzando questo foglio di carta e il nastro di mascheratura. La $k$-esima operazione ($1 \le k \le Q$) è descritta come segue a seconda del valore dell'intero $q_k$:
- Quando $q_k = 1$, questa operazione è rappresentata dagli interi $x_k, y_k, c_k$. Per ciascuna delle celle $(x_k, y_k)$, $(x_k + 1, y_k)$, $(x_k, y_k + 1)$ e $(x_k + 1, y_k + 1)$, se la cella non è coperta dal nastro di mascheratura, cambia il colore di quella cella in $c_k$. Se la cella è coperta dal nastro di mascheratura, non fare nulla su quella cella.
- Quando $q_k = 2$, questa operazione è rappresentata dagli interi $x_k, y_k$. Copri le celle $(x_k, y_k)$, $(x_k + 1, y_k)$, $(x_k, y_k + 1)$ e $(x_k + 1, y_k + 1)$ con il nastro di mascheratura.
Dopo che tutte le $Q$ operazioni sono terminate, tutto il nastro di mascheratura viene rimosso. Si noti che quando il nastro di mascheratura su una cella viene rimosso, il colore di quella cella torna ad essere lo stesso che aveva appena prima di essere coperta col nastro di mascheratura.
Date le informazioni sulle $Q$ operazioni, scrivi un programma per trovare i colori finali di tutte le celle del foglio di carta.
Vincoli
- $2 \le H \le 500$.
- $2 \le W \le 500$.
- $1 \le Q \le 200\,000$.
- $q_k$ vale $1$ oppure $2$ ($1 \le k \le Q$).
- Quando $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$).
- Quando $q_k = 2$, $1 \le x_k \le H - 1$, $1 \le y_k \le W - 1$ ($1 \le k \le Q$).
- Tutti i valori di input sono numeri interi.
Sottoproblemi
- ($32$ punti) $H = 2$, $W = 2$, $q_k = 1$ ($1 \le k \le Q$).
- ($32$ punti) $q_k = 1$ ($1 \le k \le Q$).
- ($36$ punti) Nessun vincolo aggiuntivo.
Input
L'input è fornito nel seguente formato:
$$ \begin{aligned} &H\ W\ Q \\ &(\text{Query } 1) \\ &(\text{Query } 2) \\ &\vdots \\ &(\text{Query } Q) \end{aligned} $$
Ogni $(\text{Query } k)$ ($1 \le k \le Q$) contiene diversi interi separati da spazi. Il $1$° intero è $q_k$, e il contenuto di questa riga è uno dei seguenti:
- Quando $q_k = 1$, questa riga è seguita da $3$ interi separati da spazi: $x_k, y_k, c_k$.
- Quando $q_k = 2$, questa riga è seguita da $2$ interi separati da spazi: $x_k, y_k$.
Output
Stampa i colori finali di tutte le celle del foglio di carta su $H$ righe. Sulla $i$-esima riga ($1 \le i \le H$), stampa $W$ interi separati da spazi, dove il $j$-esimo intero ($1 \le j \le W$) è il colore della cella $(i, j)$.
Esempi
Input di esempio 1
5 5 4 1 2 2 1 2 1 2 2 3 3 1 1 3 5
Output di esempio 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
Esaminiamo le $4$ operazioni in ordine.
Per la $1$ª operazione, $q_1 = 1$. Poiché le celle $(2, 2)$, $(2, 3)$, $(3, 2)$ e $(3, 3)$ non sono coperte dal nastro di mascheratura, cambia il loro colore in $1$.
A questo punto, il foglio di carta appare come segue:
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
Per la $2$ª operazione, $q_2 = 2$. Copri le celle $(1, 2)$, $(1, 3)$, $(2, 2)$ e $(2, 3)$ con il nastro di mascheratura.
A questo punto, il foglio di carta appare come segue. Si noti che è stato aggiunto un * a destra dell'intero che rappresenta il colore di una cella coperta dal nastro di mascheratura:
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
Per la $3$ª operazione, $q_3 = 2$. Copri le celle $(3, 3)$, $(3, 4)$, $(4, 3)$ e $(4, 4)$ con il nastro di mascheratura.
A questo punto, il foglio di carta appare come segue:
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
Per la $4$ª operazione, $q_4 = 1$. Poiché le celle $(1, 4)$ e $(2, 4)$ non sono coperte dal nastro di mascheratura, cambia il loro colore in $5$. Poiché le celle $(1, 3)$ e $(2, 3)$ sono coperte dal nastro di mascheratura, non fare nulla.
A questo punto, il foglio di carta appare come segue:
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
Pertanto, i colori finali di tutte le celle del foglio di carta sono quelli mostrati nell'output di esempio.
Questo esempio soddisfa i vincoli del sottoproblema $3$.
Input di esempio 2
5 5 3 1 1 1 2 1 3 3 3 1 2 4 2
Output di esempio 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
Questo esempio soddisfa i vincoli dei sottoproblemi $2, 3$.
Input di esempio 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
Output di esempio 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
Questo esempio soddisfa i vincoli del sottoproblema $3$.