Есептің шарты
JOI-кун қағаз парағы мен малярлық таспаны (бояу таспасын) қолданып, бояу ойынын ойнап отыр.
Қағаз парағы тіктөртбұрышты және оның бетіне $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$-ші ішкі есептің шектеулерін қанағаттандырады.