โจทย์ปัญหา
JOI คุงกำลังเล่นระบายสีโดยใช้กระดาษและเทปบังพ่นสี (masking tape)
กระดาษเป็นรูปสี่เหลี่ยมผืนผ้าที่มีตารางขนาด $H$ แถว และ $W$ คอลัมน์ ช่องในแถวที่ $i$ จากด้านบน ($1 \le i \le H$) และคอลัมน์ที่ $j$ จากด้านซ้าย ($1 \le j \le W$) จะเรียกว่าช่อง $(i, j)$
แต่ละช่องมีสีถูกกำหนดไว้ $1$ สี สีจะแทนด้วยจำนวนเต็ม และในตอนเริ่มต้นสีของทุกช่องคือ $0$
JOI คุงทำการดำเนินการ $Q$ ครั้งโดยใช้กระดาษแผ่นนี้และเทปบังพ่นสี การดำเนินการครั้งที่ $k$ ($1 \le k \le Q$) อธิบายได้ดังนี้ตามค่าของจำนวนเต็ม $q_k$:
- เมื่อ $q_k = 1$ การดำเนินการนี้จะแทนด้วยจำนวนเต็ม $x_k, y_k, c_k$ สำหรับแต่ละช่องในช่อง $(x_k, y_k)$, $(x_k + 1, y_k)$, $(x_k, y_k + 1)$ และ $(x_k + 1, y_k + 1)$ หากช่องนั้นไม่ได้ถูกปิดด้วยเทปบังพ่นสี ให้เปลี่ยนสีของช่องนั้นเป็น $c_k$ หากช่องนั้นถูกปิดด้วยเทปบังพ่นสีอยู่แล้ว จะไม่ทำอะไรกับช่องนั้น
- เมื่อ $q_k = 2$ การดำเนินการนี้จะแทนด้วยจำนวนเต็ม $x_k, y_k$ ให้ปิดช่อง $(x_k, y_k)$, $(x_k + 1, y_k)$, $(x_k, y_k + 1)$ และ $(x_k + 1, y_k + 1)$ ด้วยเทปบังพ่นสี
หลังจากการดำเนินการทั้ง $Q$ ครั้งเสร็จสิ้น จะลอกเทปบังพ่นสีทั้งหมดออก สังเกตว่าเมื่อลอกเทปบังพ่นสีบนช่องใดออก สีของช่องนั้นจะเหมือนกับสีของมันก่อนที่จะถูกปิดด้วยเทปบังพ่นสี
เมื่อกำหนดข้อมูลของการดำเนินการทั้ง $Q$ ครั้ง จงเขียนโปรแกรมเพื่อหาสีสุดท้ายของทุกช่องบนกระดาษ
ข้อจำกัด
- $2 \le H \le 500$
- $2 \le W \le 500$
- $1 \le Q \le 200\,000$
- $q_k$ มีค่าเป็น $1$ หรือ $2$ อย่างใดอย่างหนึ่ง ($1 \le k \le Q$)
- เมื่อ $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$)
- เมื่อ $q_k = 2$ จะได้ว่า $1 \le x_k \le H - 1$, $1 \le y_k \le W - 1$ ($1 \le k \le Q$)
- ค่าที่รับเข้ามาทั้งหมดเป็นจำนวนเต็ม
ปัญหาย่อย
- ($32$ คะแนน) $H = 2$, $W = 2$, $q_k = 1$ ($1 \le k \le Q$)
- ($32$ คะแนน) $q_k = 1$ ($1 \le k \le Q$)
- ($36$ คะแนน) ไม่มีข้อจำกัดเพิ่มเติม
ข้อมูลนำเข้า
ข้อมูลนำเข้าจะให้ในรูปแบบต่อไปนี้:
$$ \begin{aligned} &H\ W\ Q \\ &(\text{Query } 1) \\ &(\text{Query } 2) \\ &\vdots \\ &(\text{Query } Q) \end{aligned} $$
แต่ละ $(\text{Query } k)$ ($1 \le k \le Q$) ประกอบด้วยจำนวนเต็มหลายจำนวนคั่นด้วยช่องว่าง จำนวนเต็มตัวที่ $1$ คือ $q_k$ และเนื้อหาของบรรทัดนี้เป็นหนึ่งในรูปแบบต่อไปนี้:
- เมื่อ $q_k = 1$ บรรทัดนี้จะมีจำนวนเต็ม $3$ จำนวน คือ $x_k, y_k, c_k$ ตามหลังโดยคั่นด้วยช่องว่าง
- เมื่อ $q_k = 2$ บรรทัดนี้จะมีจำนวนเต็ม $2$ จำนวน คือ $x_k, y_k$ ตามหลังโดยคั่นด้วยช่องว่าง
ข้อมูลส่งออก
จงแสดงสีสุดท้ายของทุกช่องบนกระดาษเป็นจำนวน $H$ บรรทัด ในบรรทัดที่ $i$ ($1 \le i \le H$) ให้แสดงจำนวนเต็ม $W$ จำนวนคั่นด้วยช่องว่าง โดยจำนวนเต็มตัวที่ $j$ ($1 \le j \le W$) คือสีของช่อง $(i, j)$
ตัวอย่างข้อมูลนำเข้าและส่งออก
ตัวอย่างข้อมูลนำเข้า 1
5 5 4 1 2 2 1 2 1 2 2 3 3 1 1 3 5
ตัวอย่างข้อมูลส่งออก 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
มาพิจารณาการดำเนินการทั้ง $4$ ครั้งตามลำดับ
สำหรับการดำเนินการครั้งที่ $1$, $q_1 = 1$ เนื่องจากช่อง $(2, 2)$, $(2, 3)$, $(3, 2)$ และ $(3, 3)$ ทั้งหมดไม่ได้ถูกปิดด้วยเทปบังพ่นสี จึงเปลี่ยนสีเป็น $1$
ในขณะนี้ กระดาษมีลักษณะดังต่อไปนี้:
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
สำหรับการดำเนินการครั้งที่ $2$, $q_2 = 2$ ปิดช่อง $(1, 2)$, $(1, 3)$, $(2, 2)$ และ $(2, 3)$ ด้วยเทปบังพ่นสี
ในขณะนี้ กระดาษมีลักษณะดังต่อไปนี้ อนึ่ง ได้ใส่เครื่องหมาย * ไว้ทางขวาของจำนวนเต็มที่แทนสีของช่องที่ถูกปิดด้วยเทปบังพ่นสี:
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
สำหรับการดำเนินการครั้งที่ $3$, $q_3 = 2$ ปิดช่อง $(3, 3)$, $(3, 4)$, $(4, 3)$ และ $(4, 4)$ ด้วยเทปบังพ่นสี
ในขณะนี้ กระดาษมีลักษณะดังต่อไปนี้:
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
สำหรับการดำเนินการครั้งที่ $4$, $q_4 = 1$ เนื่องจากช่อง $(1, 4)$ และ $(2, 4)$ ไม่ได้ถูกปิดด้วยเทปบังพ่นสี จึงเปลี่ยนสีเป็น $5$ ส่วนช่อง $(1, 3)$ และ $(2, 3)$ ถูกปิดด้วยเทปบังพ่นสีอยู่ จึงไม่ทำอะไร
ในขณะนี้ กระดาษมีลักษณะดังต่อไปนี้:
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
ดังนั้น สีสุดท้ายของทุกช่องบนกระดาษจึงเป็นดังที่แสดงในตัวอย่างข้อมูลส่งออก
ตัวอย่างนี้เป็นไปตามข้อจำกัดของปัญหาย่อยที่ $3$
ตัวอย่างข้อมูลนำเข้า 2
5 5 3 1 1 1 2 1 3 3 3 1 2 4 2
ตัวอย่างข้อมูลส่งออก 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
ตัวอย่างนี้เป็นไปตามข้อจำกัดของปัญหาย่อยที่ $2, 3$
ตัวอย่างข้อมูลนำเข้า 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
ตัวอย่างข้อมูลส่งออก 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
ตัวอย่างนี้เป็นไปตามข้อจำกัดของปัญหาย่อยที่ $3$