Descripción
JOI-kun está jugando a colorear usando una hoja de papel y cinta de enmascarar.
La hoja de papel es rectangular y tiene dibujada una cuadrícula de $H$ filas y $W$ columnas. La celda en la $i$-ésima fila desde arriba ($1 \le i \le H$) y la $j$-ésima columna desde la izquierda ($1 \le j \le W$) se denomina celda $(i, j)$.
Cada celda tiene asignado $1$ color. Los colores se representan mediante enteros, e inicialmente el color de todas las celdas es $0$.
JOI-kun realiza $Q$ operaciones utilizando esta hoja de papel y cinta de enmascarar. La $k$-ésima operación ($1 \le k \le Q$) se describe de la siguiente manera según el valor del entero $q_k$:
- Cuando $q_k = 1$, esta operación se representa por los enteros $x_k, y_k, c_k$. Para cada una de las celdas $(x_k, y_k)$, $(x_k + 1, y_k)$, $(x_k, y_k + 1)$ y $(x_k + 1, y_k + 1)$, si la celda no está cubierta con cinta de enmascarar, se cambia el color de esa celda a $c_k$. Si la celda está cubierta con cinta de enmascarar, no se hace nada en esa celda.
- Cuando $q_k = 2$, esta operación se representa por los enteros $x_k, y_k$. Se cubren las celdas $(x_k, y_k)$, $(x_k + 1, y_k)$, $(x_k, y_k + 1)$ y $(x_k + 1, y_k + 1)$ con cinta de enmascarar.
Después de que terminan las $Q$ operaciones, se despega toda la cinta de enmascarar. Ten en cuenta que cuando se despega la cinta de enmascarar de una celda, el color de esa celda vuelve a ser el mismo que tenía justo antes de ser cubierta con la cinta de enmascarar.
Dada la información de las $Q$ operaciones, escribe un programa para encontrar los colores finales de todas las celdas de la hoja de papel.
Restricciones
- $2 \le H \le 500$.
- $2 \le W \le 500$.
- $1 \le Q \le 200\,000$.
- $q_k$ es $1$ o $2$ ($1 \le k \le Q$).
- Cuando $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$).
- Cuando $q_k = 2$, $1 \le x_k \le H - 1$, $1 \le y_k \le W - 1$ ($1 \le k \le Q$).
- Todos los valores de entrada son enteros.
Subtareas
- ($32$ puntos) $H = 2$, $W = 2$, $q_k = 1$ ($1 \le k \le Q$).
- ($32$ puntos) $q_k = 1$ ($1 \le k \le Q$).
- ($36$ puntos) Sin restricciones adicionales.
Entrada
La entrada se proporciona en el siguiente formato:
$$ \begin{aligned} &H\ W\ Q \\ &(\text{Query } 1) \\ &(\text{Query } 2) \\ &\vdots \\ &(\text{Query } Q) \end{aligned} $$
Cada $(\text{Query } k)$ ($1 \le k \le Q$) contiene varios enteros separados por espacios. El $1$-er entero es $q_k$, y el contenido de esta línea es uno de los siguientes:
- Cuando $q_k = 1$, esta línea va seguida de $3$ enteros separados por espacios: $x_k, y_k, c_k$.
- Cuando $q_k = 2$, esta línea va seguida de $2$ enteros separados por espacios: $x_k, y_k$.
Salida
Imprime los colores finales de todas las celdas de la hoja de papel en $H$ líneas. En la $i$-ésima línea ($1 \le i \le H$), imprime $W$ enteros separados por espacios, donde el $j$-ésimo entero ($1 \le j \le W$) es el color de la celda $(i, j)$.
Ejemplos
Entrada de ejemplo 1
5 5 4 1 2 2 1 2 1 2 2 3 3 1 1 3 5
Salida de ejemplo 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
Analicemos las $4$ operaciones en orden.
Para la $1$-a operación, $q_1 = 1$. Como las celdas $(2, 2)$, $(2, 3)$, $(3, 2)$ y $(3, 3)$ no están cubiertas con cinta de enmascarar, su color cambia a $1$.
En este momento, la hoja de papel se ve así:
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
Para la $2$-a operación, $q_2 = 2$. Se cubren las celdas $(1, 2)$, $(1, 3)$, $(2, 2)$ y $(2, 3)$ con cinta de enmascarar.
En este momento, la hoja de papel se ve así. Nota que se ha añadido un * a la derecha del entero que representa el color de una celda cubierta con cinta de enmascarar:
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
Para la $3$-a operación, $q_3 = 2$. Se cubren las celdas $(3, 3)$, $(3, 4)$, $(4, 3)$ y $(4, 4)$ con cinta de enmascarar.
En este momento, la hoja de papel se ve así:
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
Para la $4$-a operación, $q_4 = 1$. Como las celdas $(1, 4)$ y $(2, 4)$ no están cubiertas con cinta de enmascarar, su color cambia a $5$. Como las celdas $(1, 3)$ y $(2, 3)$ están cubiertas con cinta de enmascarar, no se hace nada.
En este momento, la hoja de papel se ve así:
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
Por lo tanto, los colores finales de todas las celdas de la hoja de papel son los que se muestran en la salida de ejemplo.
Este ejemplo cumple las restricciones de la subtarea $3$.
Entrada de ejemplo 2
5 5 3 1 1 1 2 1 3 3 3 1 2 4 2
Salida de ejemplo 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
Este ejemplo cumple las restricciones de las subtareas $2, 3$.
Entrada de ejemplo 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
Salida de ejemplo 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
Este ejemplo cumple las restricciones de la subtarea $3$.