B. Хэвлэлт шалгах

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

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

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

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

Крис "Блэйк Технологи" гэх том компанид ажилладаг. Компанийн шилдэг инженерийн хувьд Крис босоо болон хэвтээ шугамуудыг хэвлэх боломжтой хэвлэгчийг хөгжүүлэх ажилд томилогдсон. Эхний туршилтын загвар бэлэн болсон ба Крис үүнийг шалгахыг хүсч байна. Тэр таныг хэвлэлтийн үр дүнг шалгадаг програм бичихийг хүсч байна.

Хэвлэгч $n × m$ хэмжээтэй тэгш өнцөгт хүснэгт бүхий цаасан дээр хэвлэдэг. Хүснэгт нь $n$ мөртэй $m$ баганатай. Мөрүүд нь дээрээс доош $1$-с $n$ хүртэл дугаарлагдсан ба баганууд нь зүүнээс баруун тийш $1$-с $m$ хүртэлх бүхэл тоогоор дугаарлагдсан. Эхэндээ бүх нүднүүд $0$ өнгөтэй байна.

Таны програм хоёр үйлдлийг дэмждэг байх:

  1. $r_{i}$ мөрийн бүх нүдийг $a_{i}$ өнгөөр будах;
  2. $c_{i}$ баганын бүх нүдийг $a_{i}$ өнгөөр будах.

Хэрвээ $i$-р үйлдлийн үед аль хэдийн будагдчихсан нүд байвал уг нүд нь мөн адил $a_{i}$ өнгөтэй болно.

Таны програм $k$ үйлдлийн дараа гарч буй хүснэгтийг хэвлэдэг байна.

Оролт

Оролтын эхний мөрөнд гурван бүхэл тоон утга $n$, $m$ ба $k$ ($1  ≤  n,  m  ≤ 5000$, $n*m ≤ 100 000$, $1 ≤ k ≤ 100 000$) байх ба харгалзан хүснэгтийн хэмжээсүүд болон үйлдлийн тоо байна.

Дараагийн $k$ мөр бүр нэг үйлдлийн тайлбарыг агуулна:

  • $1 r_{i} a_{i}$ ($1 ≤ r_{i} ≤ n$, $1 ≤ a_{i} ≤ 10^{9}$) нь $r_{i}$ мөр $a_{i}$ өнгөөр будагдана гэдгийг илэрхийлнэ;
  • $2 c_{i} a_{i}$ ($1 ≤ c_{i} ≤ m$, $1 ≤ a_{i} ≤ 10^{9}$), нь $c_{i}$ багана $a_{i}$ өнгөөр будагдана гэдгийг илэрхийлнэ.

Гаралт

Тус бүрдээ $m$ бүхэл тоон утгаас бүрдэх $n$ ширхэг мөрийг хэвлэх ба бүх үйлдэл хийгдсэний дараах хүснэгт юм.

Орчуулсан: Г.Мэндбаяр

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

Оролт
3 3 3
1 1 3
2 2 1
1 2 2
Гаралт
3 1 3 
2 2 2 
0 1 0 
Оролт
5 3 5
1 1 1
1 3 1
1 5 1
2 1 1
2 3 1
Гаралт
1 1 1 
1 0 1 
1 1 1 
1 0 1 
1 1 1 

Тэмдэглэл

Доорх зурагт эхний жишээний гурван үйлдлийг алхам алхмаар харуулсан байна. Тухайн алхамд будагдаж буй нүднүүдийг саарал өнгөөр тэмдэглэсэн.

Сэтгэгдлүүдийг ачааллаж байна...