Aufgabenstellung

JOI-kun spielt ein Ausmalspiel mit einem Blatt Papier und Abklebeband (Masking Tape).

Das Blatt Papier ist rechteckig und darauf ist ein Gitter mit $H$ Zeilen und $W$ Spalten gezeichnet. Das Feld in der $i$-ten Zeile von oben ($1 \le i \le H$) und der $j$-ten Spalte von links ($1 \le j \le W$) wird als Feld $(i, j)$ bezeichnet.

Jedem Feld ist $1$ Farbe zugeordnet. Farben werden durch ganze Zahlen dargestellt, und zu Beginn haben alle Felder die Farbe $0$.

JOI-kun führt mit diesem Blatt Papier und dem Abklebeband $Q$ Operationen durch. Die $k$-te Operation ($1 \le k \le Q$) wird abhängig vom Wert der ganzen Zahl $q_k$ wie folgt beschrieben:

• Wenn $q_k = 1$ ist, wird diese Operation durch die ganzen Zahlen $x_k, y_k, c_k$ dargestellt. Für jedes der Felder $(x_k, y_k)$, $(x_k + 1, y_k)$, $(x_k, y_k + 1)$ und $(x_k + 1, y_k + 1)$ gilt: Wenn das Feld nicht mit Abklebeband bedeckt ist, ändere die Farbe dieses Feldes auf $c_k$. Wenn das Feld mit Abklebeband bedeckt ist, tue mit diesem Feld nichts.
• Wenn $q_k = 2$ ist, wird diese Operation durch die ganzen Zahlen $x_k, y_k$ dargestellt. Bedecke die Felder $(x_k, y_k)$, $(x_k + 1, y_k)$, $(x_k, y_k + 1)$ und $(x_k + 1, y_k + 1)$ mit Abklebeband.

Nachdem alle $Q$ Operationen abgeschlossen sind, wird das gesamte Abklebeband abgezogen. Beachte, dass beim Abziehen des Abklebebands von einem Feld die Farbe dieses Feldes genau die Farbe ist, die es unmittelbar vor dem Bedecken mit dem Abklebeband hatte.

Schreibe ein Programm, das anhand der Informationen über die $Q$ Operationen die endgültigen Farben aller Felder des Papierblatts bestimmt.

Einschränkungen

• $2 \le H \le 500$.
• $2 \le W \le 500$.
• $1 \le Q \le 200\,000$.
• $q_k$ ist entweder $1$ oder $2$ ($1 \le k \le Q$).
• Wenn $q_k = 1$ ist, gilt $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$).
• Wenn $q_k = 2$ ist, gilt $1 \le x_k \le H - 1$, $1 \le y_k \le W - 1$ ($1 \le k \le Q$).
• Alle Eingabewerte sind ganze Zahlen.

Teilaufgaben

1. ($32$ Punkte) $H = 2$, $W = 2$, $q_k = 1$ ($1 \le k \le Q$).
2. ($32$ Punkte) $q_k = 1$ ($1 \le k \le Q$).
3. ($36$ Punkte) Keine weiteren Einschränkungen.

Eingabe

Die Eingabe erfolgt im folgenden Format:

$$ \begin{aligned} &H\ W\ Q \\ &(\text{Query } 1) \\ &(\text{Query } 2) \\ &\vdots \\ &(\text{Query } Q) \end{aligned} $$

Jedes $(\text{Query } k)$ ($1 \le k \le Q$) enthält mehrere durch Leerzeichen getrennte ganze Zahlen. Die $1$-te ganze Zahl ist $q_k$, und der Inhalt dieser Zeile ist einer der folgenden:

• Wenn $q_k = 1$ ist, folgen in dieser Zeile $3$ durch Leerzeichen getrennte ganze Zahlen $x_k, y_k, c_k$.
• Wenn $q_k = 2$ ist, folgen in dieser Zeile $2$ durch Leerzeichen getrennte ganze Zahlen $x_k, y_k$.

Ausgabe

Gib die endgültigen Farben aller Felder des Papierblatts in $H$ Zeilen aus. Gib in der $i$-ten Zeile ($1 \le i \le H$) $W$ durch Leerzeichen getrennte ganze Zahlen aus, wobei die $j$-te ganze Zahl ($1 \le j \le W$) die Farbe des Feldes $(i, j)$ ist.

Beispiele

Beispieleingabe 1

5 5 4
1 2 2 1
2 1 2
2 3 3
1 1 3 5

Beispielausgabe 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

Betrachten wir die $4$ Operationen der Reihe nach.

Für die $1$-te Operation gilt $q_1 = 1$. Da die Felder $(2, 2)$, $(2, 3)$, $(3, 2)$ und $(3, 3)$ alle nicht mit Abklebeband bedeckt sind, wird ihre Farbe auf $1$ geändert.

Zu diesem Zeitpunkt sieht das Blatt Papier wie folgt aus:

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 die $2$-te Operation gilt $q_2 = 2$. Die Felder $(1, 2)$, $(1, 3)$, $(2, 2)$ und $(2, 3)$ werden mit Abklebeband bedeckt.

Zu diesem Zeitpunkt sieht das Blatt Papier wie folgt aus. Beachte, dass rechts neben der ganzen Zahl, die die Farbe eines mit Abklebeband bedeckten Feldes angibt, ein * angefügt wurde:

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 die $3$-te Operation gilt $q_3 = 2$. Die Felder $(3, 3)$, $(3, 4)$, $(4, 3)$ und $(4, 4)$ werden mit Abklebeband bedeckt.

Zu diesem Zeitpunkt sieht das Blatt Papier wie folgt aus:

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 die $4$-te Operation gilt $q_4 = 1$. Da die Felder $(1, 4)$ und $(2, 4)$ nicht mit Abklebeband bedeckt sind, wird ihre Farbe auf $5$ geändert. Da die Felder $(1, 3)$ und $(2, 3)$ mit Abklebeband bedeckt sind, wird nichts getan.

Zu diesem Zeitpunkt sieht das Blatt Papier wie folgt aus:

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

Daher sind die endgültigen Farben aller Felder des Papierblatts so wie in der Beispielausgabe dargestellt.

Dieses Beispiel erfüllt die Einschränkungen der Teilaufgabe $3$.

Beispieleingabe 2

5 5 3
1 1 1 2
1 3 3 3
1 2 4 2

Beispielausgabe 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

Dieses Beispiel erfüllt die Einschränkungen der Teilaufgaben $2, 3$.

Beispieleingabe 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

Beispielausgabe 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

Dieses Beispiel erfüllt die Einschränkungen der Teilaufgabe $3$.