| Codeforces Beta Round 71 |
|---|
| Закончено |
Лиса Кейл ехала в автобусе и смотрела в окно. За окном было поле, имеющее форму n × m прямоугольника, который был разделен на 1 × 1 квадраты. Некоторые квадраты были безжизненны, в то время как на других росли фрукты и овощи: на них росла морковь, киви или виноград.
Лиса внимательно рассмотрела поле и заметили следующую закономерность.
- Предположим все строки пронумерованы от 1 до n сверху вниз, а столбцы от 1 до m слева направо. Пусть ячейка (квадрат) в i-ой строке и j-ом столбце обозначается как (i, j).
- Во-первых, оказалось, что каждый квадрат был либо удобрен либо нет. Неудобренные квадраты оказались безжизненными, в то время как на удобренных выросли фрукты и овощи. Посадка фруктов и овощей на удобренные участки происходила слева-направо сверху-вниз: (1, 1) → ... → (1, m) → (2, 1) → ... → (2, m) → ... → (n, 1) → ... → (n, m). Неудобренные участки при посадке игнорировались.
- При посадке на ячейку была посажена одна культура (морковь, киви или виноград). Посадка культур осуществлялась по циклу, начиная с моркови. Т.е. морковь была посажена в первую удобренную клетку, во вторую — киви, в третью — виноград, в четвертую — морковь, в пятую — киви и т.д.
Следующий рисунок демонстрирует пример процедуры посадки. Здесь белые клетки обозначают удобренные ячейки, а черные — неудобренные (безжизненные).
Напишите программу, которая определяет название культуры каждой из заданных t клеток.
Первая строка содержит четыре положительных целых числа n, m, k, t (1 ≤ n ≤ 4·104, 1 ≤ m ≤ 4·104, 1 ≤ k ≤ 103, 1 ≤ t ≤ 103), обозначающих высоту, ширину, количество неудобренных клеток и количество клеток для определения культур на них.
Следующие k строк содержат пары координат a, b (1 ≤ a ≤ n, 1 ≤ b ≤ m), которые обозначают, что клетки (a, b) являются неудобренными. Гарантируется, что никакая клетка не встречается дважды в этом списке.
Следующие t строк содержат координаты i, j (1 ≤ i ≤ n, 1 ≤ j ≤ m), которые обозначают, что для клетки (i, j) надо определить культуру на ней.
Для каждой из t заданных клеток выведите:
- «Waste» — если клетка безжизненна,
- «Carrots», «Kiwis» или «Grapes» — если там растет морковь, киви или виноград соответственно.
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
Пример соответствует картинке из условия.
