Крис "Блэйк Технологи" гэх том компанид ажилладаг. Компанийн шилдэг инженерийн хувьд Крис босоо болон хэвтээ шугамуудыг хэвлэх боломжтой хэвлэгчийг хөгжүүлэх ажилд томилогдсон. Эхний туршилтын загвар бэлэн болсон ба Крис үүнийг шалгахыг хүссэн. Тэр таныг хэвлэлтийн үр дүнг шалгадаг програм бичихийг хүсч байна.
Хэвлэгч n×m хэмжээтэй тэгш өнцөгт хүснэгт бүхий цаасан дээр хэвлэдэг. Хүснэгт нь n мөртэй m баганатай. Мөрүүд нь дээрээс доош 1-с n хүртэл дугаарлагдсан ба баганууд нь зүүнээс баруун тийш 1-с m хүртэлх бүхэл тоогоор дугаарлагдсан. Эхэндээ бүх нүднүүд 0 өнгөтэй байна.
Таны програм хоёр үйлдлийг дэмждэг байх:
1-р эхэлбэл ri мөрийн бүх нүдийг ai өнгөөр будах;
2-р эхэлбэл ci баганын бүх нүдийг ai өнгөөр будах.
Хэрвээ i-р үйлдлийн үед аль хэдийн будагдчихсан нүд байвал уг нүд нь мөн адил ai өнгөтэй болно.
Таны програм k үйлдлийн дараа гарч буй хүснэгтийг хэвлэх юм.
Оролтын эхний мөрөнд гурван бүхэл тоон утга n, m ба k байх ба харгалзан хүснэгтийн хэмжээсүүд болон үйлдлийн тоо байна.
Дараагийн k мөр бүр үйлдлийн тайлбарыг агуулна:
1, ri, ai нь ri мөр ai өнгөөр будагдана гэдгийг илэрхийлнэ;
2, ci, ai , нь ci багана ai өнгөөр будагдана гэдгийг илэрхийлнэ.
Тус бүрдээ m бүхэл тоон утгаас бүрдэх n ширхэг мөрийг хэвлэх ба бүх үйлдэл хийгдсэний дараах хүснэгт юм.
1≤n,m≤5000,n×m≤100000,1≤k≤100000
1≤ri≤n,1≤ai≤109
1≤ci≤m,1≤ai≤109
3 3 3 1 1 3 2 2 1 1 2 2
3 1 3 2 2 2 0 1 0