B. Бяцхан Артем ба Матриц

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Бяцхан Артем цахилгаан бараануудад ихээхэн дуртай нэгэн юм. Тэрээр маш их цагийг олон төрлийн ялгаатай схемүүд хийж өнгөрүүлдэг бөгөөд хамгийн ойр байх нэгэн цахилгаан барааны дэлгүүрт шинэлэг бараа хайж үзэх дуртай байжээ. Шинэ удирдлагын элемент уг дэлгүүрт саяхан ирсэн бөгөөд Артем тэр даруй уг элементийг худалдан авчээ.

Уг элемент нь бүхэл тоон хэмжээтэй $n × m$ матрицийн мэдээллийг хадгалж чаддаг байв. Уг элементийн оролтын хэсэгт нийтдээ $n + m$ ширхэг оролт байх бөгөөд өөрөөр хэлбэл мөр болон багана бүр нь дохио хүлээн авч чаддаг байв. Дохио ямар нэгэн мөрөнд харгалзан оролтод орж ирэх үед уг мөр нь зүүн тийш цикл хэлбэрээр сэлгэлт хийх бөгөөд тодруулбал уг мөрийн эхний элемент нь сүүлийн элемент болох ба 2-дахь элемент нь эхний элемент болно гэх мэтчилэн үргэлжлэх юм. Дохио ямар нэгэн баганад харгалзан оролтод орж ирэх үед уг багана нь дээшээ чиглэлд цикл хэлбэрээр сэлгэлт хийх бөгөөд тодруулбал уг баганын эхний элемент нь уг баганын сүүлийн элемент болох ба 2-дахь элемент нь эхний элемент болно гэх мэтчилэн үргэлжлэх ажээ. Мөрүүд нь дээрээс доош хүртэл $1$-ээс $n$ хүртэлх бүхэл тоонуудаар дугаарлагдсан байх бөгөөд баганууд нь зүүнээс баруун хүртэл $1$-ээс $m$ хүртэлх бүхэл тоонуудаар дугаарлагдсан байх юм.

Артем уг элементийг хэрэглэхээсээ өмнө сайтар судлахыг хүсжээ. Үүний тулд тэрээр $q$ ширхэг ээлжээс тогтох нэгэн туршилт явуулахаар болов. Ээлж болгонд тэрээр ямар нэгэн оролт уруу дохио явуулах эсвэл матрицийн ямар нэгэн байрлал дээр ямар тоо хадгалагдсан байгааг шалгана.

Артем өөрийн туршилтаа явуулж дууссан бөгөөд туршилтын үр дүнг бичиж авсан боловч өөрийн чип-ээ алга болгосон байв. Артем-д туслан туршилтын үр дүнтэй тохирох ямар нэгэн анхны матрицийг олж өгч тусална уу. Туршилтын үр дүн нь үнэн зөв байх бөгөөд өөрөөр хэлбэл уг үр дүнтэй тохирох дор хаяж нэг ширхэг боломжит матриц оршин байх юм.

Оролт

Оролтын эхний мөрөнд 3 бүхэл тоо $n$, $m$ болон $q$ ($1 ≤ n, m ≤ 100, 1 ≤ q ≤ 10 000$) өгөгдөх ба эдгээр нь харгалзан матрицын хэмжээс болон туршилтын явцад хийх нийт ээлжийн тоог тус тус илэрхийлнэ.

Дараагийн $q$ мөрөнд ээлжүүдийг дүрслэх бөгөөд нэг мөрөнд нэг ээлжийн тайлбар өгөгдөнө. Ээлж болгон нь $t_{i}$ ($1 ≤ t_{i} ≤ 3$) гэсэн бүхэл тоогоор эхлэх ба энэ нь уг ээлжийн үйлдлийн төрлийг илэрхийлэх юм. Эхний болон 2-дахь төрлийн үйлдлийн хувьд уг тооны араас бүхэл тоо $r_{i}$ ($1 ≤ r_{i} ≤ n$) эсвэл $c_{i}$ ($1 ≤ c_{i} ≤ m$) өгөгдөх ба 3-дахь төрлийн үйлдлийн хувьд уг тооны араас $r_{i}$, $c_{i}$ болон $x_{i}$ ($1 ≤ r_{i} ≤ n$, $1 ≤ c_{i} ≤ m$, $ - 10^{9} ≤ x_{i} ≤ 10^{9}$) гэсэн 3 ширхэг бүхэл тоо өгөгдөх юм.

Эхний төрлийн ($t_{i} = 1$) үйлдлийн хувьд дохио нь $r_{i}$-р мөрөнд ирнэ гэсэн утгатай бөгөөд уг мөр нь цикл хэлбэрээр сэлгэлт хийх юм. 2-дахь төрлийн ($t_{i} = 2$) үйлдлийн хувьд дохио нь $c_{i}$-р баганад ирнэ гэсэн утгатай бөгөөд уг багана нь мөн адил цикл хэлбэрээр сэлгэлт хийнэ. Сүүлийн буюу 3-дахь төрлийн үйлдлийн хувьд $r_{i}$-р мөр болон $c_{i}$-р баганад байрлах нүдэнд $x_{i}$ гэсэн утга байгааг илэрхийлж байгаа юм.

Гаралт

Ямар нэгэн боломжит анхны матрицийн тайлбар буюу тус бүр нь $m$ ширхэг бүхэл тоо агуулах $n$ ширхэг мөр хэвлэнэ үү. Гаралтын тоонууд нь бүгд бүхэл тоонууд байх бөгөөд абсолют утгууд нь $10^{9}$-өөс хэтрэхгүй байна.

Хэрэв олон тооны боломжит хариултууд байвал тэдгээрийн алийг нь ч хэвлэсэн болно.

Орчуулсан: Баатархүү

Жишээ тэстүүд

Оролт
2 2 6
2 1
2 2
3 1 1 1
3 2 2 2
3 1 2 8
3 2 1 8
Гаралт
8 2 
1 8 
Оролт
3 3 2
1 2
3 2 2 5
Гаралт
0 0 0 
0 0 5 
0 0 0 
Сэтгэгдлүүдийг ачааллаж байна...