نص المسألة

يلعب JOI-kun لعبة التلوين باستخدام ورقة وشريط تغطية لاصق (masking tape).

الورقة مستطيلة الشكل، ومقسّمة إلى شبكة من $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$).
• جميع القيم المدخلة هي أعداد صحيحة.

المهام الفرعية

1. ($32$ نقطة) $H = 2$، $W = 2$، $q_k = 1$ ($1 \le k \le Q$).
2. ($32$ نقطة) $q_k = 1$ ($1 \le k \le Q$).
3. ($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$.