Deskripsi Masalah
JOI-kun sedang bermain mewarnai menggunakan selembar kertas dan selotip pelindung (masking tape).
Selembar kertas tersebut berbentuk persegi panjang dengan kisi-kisi berukuran $H$ baris dan $W$ kolom yang tergambar di atasnya. Petak pada baris ke-$i$ dari atas ($1 \le i \le H$) dan kolom ke-$j$ dari kiri ($1 \le j \le W$) disebut petak $(i, j)$.
Setiap petak memiliki $1$ warna yang ditetapkan. Warna direpresentasikan oleh bilangan bulat, dan pada awalnya warna semua petak adalah $0$.
JOI-kun melakukan $Q$ operasi menggunakan kertas ini dan selotip pelindung. Operasi ke-$k$ ($1 \le k \le Q$) dijelaskan sebagai berikut bergantung pada nilai bilangan bulat $q_k$:
- Ketika $q_k = 1$, operasi ini direpresentasikan oleh bilangan bulat $x_k, y_k, c_k$. Untuk masing-masing petak $(x_k, y_k)$, $(x_k + 1, y_k)$, $(x_k, y_k + 1)$, dan $(x_k + 1, y_k + 1)$, jika petak tersebut tidak tertutup selotip pelindung, ubah warna petak tersebut menjadi $c_k$. Jika petak tersebut tertutup selotip pelindung, jangan lakukan apa-apa pada petak tersebut.
- Ketika $q_k = 2$, operasi ini direpresentasikan oleh bilangan bulat $x_k, y_k$. Tutupi petak $(x_k, y_k)$, $(x_k + 1, y_k)$, $(x_k, y_k + 1)$, dan $(x_k + 1, y_k + 1)$ dengan selotip pelindung.
Setelah semua $Q$ operasi selesai, semua selotip pelindung dilepas. Perhatikan bahwa ketika selotip pelindung pada suatu petak dilepas, warna petak tersebut menjadi sama dengan warnanya tepat sebelum ditutupi selotip pelindung.
Diberikan informasi mengenai $Q$ operasi tersebut, buatlah program untuk mencari warna akhir dari semua petak pada kertas.
Batasan
- $2 \le H \le 500$.
- $2 \le W \le 500$.
- $1 \le Q \le 200\,000$.
- $q_k$ bernilai $1$ atau $2$ ($1 \le k \le Q$).
- Ketika $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$).
- Ketika $q_k = 2$, $1 \le x_k \le H - 1$, $1 \le y_k \le W - 1$ ($1 \le k \le Q$).
- Semua nilai masukan adalah bilangan bulat.
Subsoal
- ($32$ poin) $H = 2$, $W = 2$, $q_k = 1$ ($1 \le k \le Q$).
- ($32$ poin) $q_k = 1$ ($1 \le k \le Q$).
- ($36$ poin) Tidak ada batasan tambahan.
Masukan
Masukan diberikan dalam format berikut:
$$ \begin{aligned} &H\ W\ Q \\ &(\text{Query } 1) \\ &(\text{Query } 2) \\ &\vdots \\ &(\text{Query } Q) \end{aligned} $$
Setiap $(\text{Query } k)$ ($1 \le k \le Q$) berisi beberapa bilangan bulat yangisahkan oleh spasi. Bilangan bulat ke-$1$ adalah $q_k$, dan isi baris ini adalah salah satu dari berikut:
- Ketika $q_k = 1$, baris ini diikuti oleh $3$ bilangan bulat yang dipisahkan spasi: $x_k, y_k, c_k$.
- Ketika $q_k = 2$, baris ini diikuti oleh $2$ bilangan bulat yang dipisahkan spasi: $x_k, y_k$.
Keluaran
Keluarkan warna akhir dari semua petak pada kertas dalam $H$ baris. Pada baris ke-$i$ ($1 \le i \le H$), keluarkan $W$ bilangan bulat yang dipisahkan spasi, di mana bilangan bulat ke-$j$ ($1 \le j \le W$) adalah warna petak $(i, j)$.
Contoh Masukan dan Keluaran
Contoh Masukan 1
5 5 4 1 2 2 1 2 1 2 2 3 3 1 1 3 5
Contoh Keluaran 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
Mari kita perhatikan ke-$4$ operasi tersebut secara berurutan.
Untuk operasi ke-$1$, $q_1 = 1$. Karena petak $(2, 2)$, $(2, 3)$, $(3, 2)$, dan $(3, 3)$ semuanya tidak tertutup selotip pelindung, ubah warnanya menjadi $1$.
Pada saat ini, kertas terlihat seperti berikut:
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
Untuk operasi ke-$2$, $q_2 = 2$. Tutupi petak $(1, 2)$, $(1, 3)$, $(2, 2)$, dan $(2, 3)$ dengan selotip pelindung.
Pada saat ini, kertas terlihat seperti berikut. Perhatikan bahwa tanda * ditambahkan di sebelah kanan bilangan bulat yang menyatakan warna petak yang tertutup selotip pelindung:
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
Untuk operasi ke-$3$, $q_3 = 2$. Tutupi petak $(3, 3)$, $(3, 4)$, $(4, 3)$, dan $(4, 4)$ dengan selotip pelindung.
Pada saat ini, kertas terlihat seperti berikut:
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
Untuk operasi ke-$4$, $q_4 = 1$. Karena petak $(1, 4)$ dan $(2, 4)$ tidak tertutup selotip pelindung, ubah warnanya menjadi $5$. Karena petak $(1, 3)$ dan $(2, 3)$ tertutup selotip pelindung, jangan lakukan apa-apa.
Pada saat ini, kertas terlihat seperti berikut:
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
Oleh karena itu, warna akhir dari semua petak pada kertas adalah seperti yang ditunjukkan pada contoh keluaran.
Contoh ini memenuhi batasan Subsoal $3$.
Contoh Masukan 2
5 5 3 1 1 1 2 1 3 3 3 1 2 4 2
Contoh Keluaran 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
Contoh ini memenuhi batasan Subsoal $2, 3$.
Contoh Masukan 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
Contoh Keluaran 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
Contoh ini memenuhi batasan Subsoal $3$.