B. Ѳнгѳт талбай

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

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

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

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

Сиэл үнэг автобусаар явж байхдаа том талбай харжээ. Уг талбай $1 \times 1$ нүднүүдээс бүрдэх $n × m$ хэмжээтэй тэгш ѳнцѳгт хэлбэртэй байв. Зарим нүд хоосон байсан бѳгѳѳд үлдсэн нүд бүр лууван эсвэл киви юмуу усан үзмийн аль нэг нь ургасан байв.

Талбайг анхааралтай ажигласны дараа Сиэл ургамлуудыг дараах байдлаар тарьсныг олж мэдлээ:

  • Мѳрүүд дээрээс доош $1$-ээс $n$, баганууд зүүнээс баруун тийш $1$-ээс $m$ хүртэл дугаарлагдсан, мѳн $i$-р мѳр, $j$-р багана дахь нүдийг $(i, j)$-ээр илэрхийлнэ гэж үзье.
  • Эхлээд, нүд бүр эсвэл хоосон, эсвэл ургацтай байна. Ургамлуудыг ургацтай нүднүүдэд $(1, 1) → ... → (1, m) → (2, 1) → ... → (2, m) → ... → (n, 1) → ... → (n, m)$ дарааллаар суулгасан байв. Хоосон нүднүүд орхигдсон байна.
  • Ургамлуудыг (лууван эсвэл киви юмуу усан үзэм) нүд бүрт, нэг нүдэнд суулгасны дараа нѳгѳѳд гэх маягаар давталттайгаар тарьжээ. Эхний нүдэнд лууван, хоёрдахь нүдэнд киви, гуравдахь нүдэнд усан үзэм, дѳрѳвдэх нүдэнд лууван, тавдахь нүдэнд киви гэх мэтээр тарьсан байна.

Доорх зурганд энэ ажиллагааг зургаар үзүүлжээ. Энд цагаан нүд ургацтайг, хар нүд хоосонг илэрхийлнэ.

Одоо тэр зарим нэг нүднүүд ямар ургамалтайг хэрхэн тодорхойлохыг сонирхож байна.

Оролт

Эхний мѳрѳнд талбайн ѳргѳн, урт, хоосон нүдний тоо, ямар ургамалтайг мэдэхийг хүсч байгаа нүдний тоо болох $n$, $m$, $k$, $t$ ($1 ≤ n ≤ 4·10^4$, $1 ≤ m ≤ 4·10^4$, $1 ≤ k ≤ 10^3$, $1 ≤ t ≤ 10^3$) дѳрвѳн бүхэл тоо ѳгѳгднѳ.

Дараагийн $k$ нүд бүрт хоосон нүдийг тодорхойлох $a$, $b$ ($1 ≤ a ≤ n$, $1 ≤ b ≤ m$) хоёр бүхэл тоо ѳгѳгднѳ. Энэ хэсэгт ямар ч байсан нэг нүд хоёр удаа гарахгүй.

Дараагийн $t$ нүд бүрт ямар ургамалтайг мэдэхийг хүсч буй нүд болох $i$, $j$ ($1 ≤ i ≤ n$, $1 ≤ j ≤ m$) хоёр бүхэл тоо ѳгѳгднѳ.

Гаралт

Хүсэлт бүрт хэрвээ уг нүд хоосон бол $Waste$ гэж хэвлэ. Бусад үед уг нүдэн дэх ургамлын нэрийг, лууван бол $Carrots$, киви бол $Kiwis$, усан үзэм бол $Grapes$ гэж хэвлэ.

Орчуулсан: Sugardorj

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

Оролт
4 5 5 6
4 3
1 3
3 3
2 5
3 2
1 3
1 4
2 3
2 4
1 1
1 1
Гаралт
Waste
Grapes
Carrots
Kiwis
Carrots
Carrots

Тэмдэглэл

The sample corresponds to the figure in the statement.

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