Énoncé
JOI-kun joue à colorier à l'aide d'une feuille de papier et de ruban de masquage.
La feuille de papier est rectangulaire et comporte une grille de $H$ lignes et $W$ colonnes. La case située à la $i$-ème ligne depuis le haut ($1 \le i \le H$) et à la $j$-ème colonne depuis la gauche ($1 \le j \le W$) est appelée case $(i, j)$.
Chaque case possède $1$ couleur attribuée. Les couleurs sont représentées par des entiers, et initialement la couleur de toutes les cases est $0$.
JOI-kun effectue $Q$ opérations à l'aide de cette feuille de papier et de ruban de masquage. La $k$-ème opération ($1 \le k \le Q$) est décrite comme suit selon la valeur de l'entier $q_k$ :
- Lorsque $q_k = 1$, cette opération est représentée par les entiers $x_k, y_k, c_k$. Pour chacune des cases $(x_k, y_k)$, $(x_k + 1, y_k)$, $(x_k, y_k + 1)$ et $(x_k + 1, y_k + 1)$, si la case n'est pas recouverte de ruban de masquage, on change la couleur de cette case en $c_k$. Si la case est recouverte de ruban de masquage, on ne fait rien sur cette case.
- Lorsque $q_k = 2$, cette opération est représentée par les entiers $x_k, y_k$. On recouvre les cases $(x_k, y_k)$, $(x_k + 1, y_k)$, $(x_k, y_k + 1)$ et $(x_k + 1, y_k + 1)$ avec du ruban de masquage.
Une fois les $Q$ opérations terminées, on retire tout le ruban de masquage. Notez que lorsqu'on retire le ruban de masquage d'une case, la couleur de cette case redevient identique à celle qu'elle avait juste avant d'être recouverte par le ruban de masquage.
Étant donné les informations sur les $Q$ opérations, écrivez un programme pour déterminer les couleurs finales de toutes les cases de la feuille de papier.
Contraintes
- $2 \le H \le 500$.
- $2 \le W \le 500$.
- $1 \le Q \le 200\,000$.
- $q_k$ vaut soit $1$ soit $2$ ($1 \le k \le Q$).
- Lorsque $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$).
- Lorsque $q_k = 2$, $1 \le x_k \le H - 1$, $1 \le y_k \le W - 1$ ($1 \le k \le Q$).
- Toutes les valeurs d'entrée sont des entiers.
Sous-tâches
- ($32$ points) $H = 2$, $W = 2$, $q_k = 1$ ($1 \le k \le Q$).
- ($32$ points) $q_k = 1$ ($1 \le k \le Q$).
- ($36$ points) Aucune contrainte supplémentaire.
Entrée
L'entrée est donnée dans le format suivant :
$$ \begin{aligned} &H\ W\ Q \\ &(\text{Query } 1) \\ &(\text{Query } 2) \\ &\vdots \\ &(\text{Query } Q) \end{aligned} $$
Chaque $(\text{Query } k)$ ($1 \le k \le Q$) contient plusieurs entiers séparés par des espaces. Le $1$-er entier est $q_k$, et le contenu de cette ligne est l'un des suivants :
- Lorsque $q_k = 1$, cette ligne est suivie de $3$ entiers séparés par des espaces : $x_k, y_k, c_k$.
- Lorsque $q_k = 2$, cette ligne est suivie de $2$ entiers séparés par des espaces : $x_k, y_k$.
Sortie
Affichez les couleurs finales de toutes les cases de la feuille de papier sur $H$ lignes. Sur la $i$-ème ligne ($1 \le i \le H$), affichez $W$ entiers séparés par des espaces, où le $j$-ème entier ($1 \le j \le W$) est la couleur de la case $(i, j)$.
Exemples
Exemple d'entrée 1
5 5 4 1 2 2 1 2 1 2 2 3 3 1 1 3 5
Exemple de sortie 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
Examinons les $4$ opérations dans l'ordre.
Pour la $1$-re opération, $q_1 = 1$. Comme les cases $(2, 2)$, $(2, 3)$, $(3, 2)$ et $(3, 3)$ ne sont pas recouvertes de ruban de masquage, leur couleur devient $1$.
À ce moment, la feuille de papier ressemble à ceci :
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
Pour la $2$-e opération, $q_2 = 2$. On recouvre les cases $(1, 2)$, $(1, 3)$, $(2, 2)$ et $(2, 3)$ de ruban de masquage.
À ce moment, la feuille de papier ressemble à ceci. Notez qu'un * a été ajouté à droite de l'entier représentant la couleur d'une case recouverte de ruban de masquage :
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
Pour la $3$-e opération, $q_3 = 2$. On recouvre les cases $(3, 3)$, $(3, 4)$, $(4, 3)$ et $(4, 4)$ de ruban de masquage.
À ce moment, la feuille de papier ressemble à ceci :
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
Pour la $4$-e opération, $q_4 = 1$. Comme les cases $(1, 4)$ et $(2, 4)$ ne sont pas recouvertes de ruban de masquage, leur couleur devient $5$. Comme les cases $(1, 3)$ et $(2, 3)$ sont recouvertes de ruban de masquage, on ne fait rien.
À ce moment, la feuille de papier ressemble à ceci :
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
Par conséquent, les couleurs finales de toutes les cases de la feuille de papier sont telles qu'indiquées dans l'exemple de sortie.
Cet exemple satisfait les contraintes de la sous-tâche $3$.
Exemple d'entrée 2
5 5 3 1 1 1 2 1 3 3 3 1 2 4 2
Exemple de sortie 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
Cet exemple satisfait les contraintes des sous-tâches $2, 3$.
Exemple d'entrée 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
Exemple de sortie 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
Cet exemple satisfait les contraintes de la sous-tâche $3$.