Đề bài
JOI-kun đang chơi trò tô màu bằng một tờ giấy và băng dính che sơn.
Tờ giấy có dạng hình chữ nhật, được kẻ lưới gồm $H$ hàng và $W$ cột. Ô ở hàng thứ $i$ tính từ trên xuống ($1 \le i \le H$) và cột thứ $j$ tính từ trái sang ($1 \le j \le W$) được gọi là ô $(i, j)$.
Mỗi ô được gán $1$ màu. Màu sắc được biểu diễn bằng số nguyên, và ban đầu màu của tất cả các ô đều là $0$.
JOI-kun thực hiện $Q$ thao tác bằng tờ giấy này và băng dính che sơn. Thao tác thứ $k$ ($1 \le k \le Q$) được mô tả như sau tùy thuộc vào giá trị của số nguyên $q_k$:
- Khi $q_k = 1$, thao tác này được biểu diễn bởi các số nguyên $x_k, y_k, c_k$. Với mỗi ô trong các ô $(x_k, y_k)$, $(x_k + 1, y_k)$, $(x_k, y_k + 1)$, $(x_k + 1, y_k + 1)$, nếu ô đó không bị phủ băng dính che sơn thì đổi màu của ô đó thành $c_k$. Nếu ô đó đang bị phủ băng dính che sơn thì không làm gì với ô đó.
- Khi $q_k = 2$, thao tác này được biểu diễn bởi các số nguyên $x_k, y_k$. Phủ băng dính che sơn lên các ô $(x_k, y_k)$, $(x_k + 1, y_k)$, $(x_k, y_k + 1)$, $(x_k + 1, y_k + 1)$.
Sau khi kết thúc cả $Q$ thao tác, toàn bộ băng dính che sơn được bóc ra. Lưu ý rằng khi bóc băng dính che sơn trên một ô, màu của ô đó sẽ giống với màu của nó ngay trước khi bị phủ băng dính che sơn.
Cho thông tin về $Q$ thao tác, hãy viết chương trình tìm màu cuối cùng của tất cả các ô trên tờ giấy.
Giới hạn
- $2 \le H \le 500$.
- $2 \le W \le 500$.
- $1 \le Q \le 200\,000$.
- $q_k$ là $1$ hoặc $2$ ($1 \le k \le Q$).
- Khi $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$).
- Khi $q_k = 2$, $1 \le x_k \le H - 1$, $1 \le y_k \le W - 1$ ($1 \le k \le Q$).
- Tất cả các giá trị đầu vào đều là số nguyên.
Subtask
- ($32$ điểm) $H = 2$, $W = 2$, $q_k = 1$ ($1 \le k \le Q$).
- ($32$ điểm) $q_k = 1$ ($1 \le k \le Q$).
- ($36$ điểm) Không có giới hạn bổ sung.
Dữ liệu vào
Dữ liệu vào được cho theo định dạng sau:
$$ \begin{aligned} &H\ W\ Q \\ &(\text{Query } 1) \\ &(\text{Query } 2) \\ &\vdots \\ &(\text{Query } Q) \end{aligned} $$
Mỗi $(\text{Query } k)$ ($1 \le k \le Q$) chứa một số số nguyên cách nhau bởi dấu cách. Số nguyên thứ $1$ là $q_k$, và nội dung của dòng này là một trong hai dạng sau:
- Khi $q_k = 1$, theo sau trên dòng này là $3$ số nguyên $x_k, y_k, c_k$ cách nhau bởi dấu cách.
- Khi $q_k = 2$, theo sau trên dòng này là $2$ số nguyên $x_k, y_k$ cách nhau bởi dấu cách.
Dữ liệu ra
In ra màu cuối cùng của tất cả các ô trên tờ giấy trong $H$ dòng. Ở dòng thứ $i$ ($1 \le i \le H$), in ra $W$ số nguyên cách nhau bởi dấu cách, trong đó số nguyên thứ $j$ ($1 \le j \le W$) là màu của ô $(i, j)$.
Ví dụ
Ví dụ đầu vào 1
5 5 4 1 2 2 1 2 1 2 2 3 3 1 1 3 5
Ví dụ đầu ra 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
Ta xét lần lượt $4$ thao tác.
Với thao tác thứ $1$, $q_1 = 1$. Vì các ô $(2, 2)$, $(2, 3)$, $(3, 2)$, $(3, 3)$ đều không bị phủ băng dính che sơn nên ta đổi màu của chúng thành $1$.
Lúc này, tờ giấy có trạng thái như sau:
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
Với thao tác thứ $2$, $q_2 = 2$. Phủ băng dính che sơn lên các ô $(1, 2)$, $(1, 3)$, $(2, 2)$, $(2, 3)$.
Lúc này, tờ giấy có trạng thái như sau. Lưu ý rằng dấu * được gắn vào bên phải số nguyên biểu diễn màu của ô bị phủ băng dính che sơn:
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
Với thao tác thứ $3$, $q_3 = 2$. Phủ băng dính che sơn lên các ô $(3, 3)$, $(3, 4)$, $(4, 3)$, $(4, 4)$.
Lúc này, tờ giấy có trạng thái như sau:
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
Với thao tác thứ $4$, $q_4 = 1$. Vì các ô $(1, 4)$, $(2, 4)$ không bị phủ băng dính che sơn nên ta đổi màu của chúng thành $5$. Vì các ô $(1, 3)$, $(2, 3)$ đang bị phủ băng dính che sơn nên ta không làm gì.
Lúc này, tờ giấy có trạng thái như sau:
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
Do đó, màu cuối cùng của tất cả các ô trên tờ giấy giống như trong ví dụ đầu ra.
Ví dụ này thỏa mãn các giới hạn của Subtask $3$.
Ví dụ đầu vào 2
5 5 3 1 1 1 2 1 3 3 3 1 2 4 2
Ví dụ đầu ra 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
Ví dụ này thỏa mãn các giới hạn của Subtask $2, 3$.
Ví dụ đầu vào 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
Ví dụ đầu ra 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
Ví dụ này thỏa mãn các giới hạn của Subtask $3$.