תיאור הבעיה
JOI-kun משחק במשחק צביעה באמצעות גיליון נייר ונייר דבק (מסקינגטייפ).
גיליון הנייר הוא מלבני, ומצוירת עליו רשת של $H$ שורות ו-$W$ עמודות. התא בשורה ה-$i$ מלמעלה ($1 \le i \le H$) ובעמודה ה-$j$ משמאל ($1 \le j \le W$) נקרא תא $(i, j)$.
לכל תא מוקצה צבע $1$. צבעים מיוצגים על ידי מספרים שלמים, ובהתחלה הצבע של כל התאים הוא $0$.
JOI-kun מבצע $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$.