JOI đang chơi tô màu bằng giấy và băng dính che sơn.

Tờ giấy hình chữ nhật được chia thành lưới gồm \(H\) hàng và \(W\) cột. Gọi ô ở hàng thứ \(i\) từ trên xuống (\(1 \le i \le H\)), cột thứ \(j\) từ trái sang (\(1 \le j \le W\)) là ô \((i, j)\).

Mỗi ô có một màu, được biểu diễn bằng một số nguyên. Ban đầu, màu của tất cả các ô đều là \(0\).

JOI thực hiện \(Q\) thao tác với tờ giấy và băng dính. Thao tác thứ \(k\) (\(1 \le k \le Q\)) được mô tả tùy theo giá trị của số nguyên \(q_k\) như sau:

• Nếu \(q_k = 1\), thao tác được cho bởi các số nguyên \(x_k, y_k, c_k\). Xét từng ô trong bốn ô \((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ị băng dính che phủ thì đổi màu ô thành \(c_k\); nếu ô bị băng dính che phủ thì không làm gì với ô đó.
• Nếu \(q_k = 2\), thao tác được cho bởi các số nguyên \(x_k, y_k\). Che phủ bốn ô \((x_k, y_k)\), \((x_k + 1, y_k)\), \((x_k, y_k + 1)\), \((x_k + 1, y_k + 1)\) bằng băng dính.

Sau khi hoàn thành \(Q\) thao tác, JOI bóc tất cả băng dính ra. Khi bóc băng dính khỏi một ô, màu của ô đó vẫn là màu ngay trước khi ô bị băng dính che phủ.

Cho thông tin về \(Q\) thao tác, hãy xác định màu cuối cùng của tất cả các ô trên tờ giấy.

Dữ liệu vào

Dữ liệu vào có dạng:

H W Q
(Query 1)
(Query 2)
...
(Query Q)

Mỗi dòng \((\mathrm{Query}\ k)\) (\(1 \le k \le Q\)) chứa các số nguyên cách nhau bởi dấu cách. Số nguyên đầu tiên là \(q_k\), và dòng này có một trong hai dạng:

• Nếu \(q_k = 1\): 1 x_k y_k c_k.
• Nếu \(q_k = 2\): 2 x_k y_k.

Dữ liệu ra

In màu cuối cùng của tất cả các ô trên \(H\) dòng. Dòng thứ \(i\) (\(1 \le i \le H\)) chứa \(W\) số nguyên cách nhau bởi dấu cách, trong đó số thứ \(j\) (\(1 \le j \le W\)) là màu của ô \((i, j)\).

Ràng buộc

• \(2 \le H \le 500\).
• \(2 \le W \le 500\).
• \(1 \le Q \le 200\,000\).
• \(q_k \in \{1, 2\}\) (\(1 \le k \le Q\)).
• Nếu \(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\)).
• Nếu \(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ị trong dữ liệu vào đều là số nguyên.

Chấm điểm

1. \(32\) điểm: \(H = 2\), \(W = 2\), \(q_k = 1\) với mọi \(1 \le k \le Q\).
2. \(32\) điểm: \(q_k = 1\) với mọi \(1 \le k \le Q\).
3. \(36\) điểm: Không có ràng buộc bổ sung.

Ví dụ

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

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

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

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

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

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

5 5 3
1 1 1 2
1 3 3 3
1 2 4 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

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

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

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.