| Good Bye 2016 |
|---|
| Закончено |
Обратите внимание на информацию о том как сбрасывать буфер вывода (делать операцию 'flush'), указанную в секции «Выходные данные».
Беарляндия представляет из себя клетчатое поле, состоящее из h строк и w столбцов. Строки пронумерованы от 1 до h сверху вниз. Столбцы пронумерованы от 1 до w слева направо. Каждая клетка является либо свободной (обозначается символом «.» во входных данных) либо постоянно заблокированной (обозначается символом «#»).
Беарляндия — холодная страна и снегопады часто затрудняют путешествия. Каждый день некоторое небольшое количество клеток оказываются временно заблокированными из-за снега. Обратите внимание, что такая блокировка клетки работает только внутри одного конкретного дня и на следующий день любые из заблокированных клеток могут оказаться свободными (если только они не будут снова временно заблокированы).
Между двумя клетками можно перемещаться напрямую, если у них есть общая сторона и ни одна из них не является ни постоянно ни временно заблокированной.
Лимак — маленький полярный медвежонок, которой живёт в Беарляндии. Его дом расположен в левой верхней клетке поля, а школа в правой нижней клетке. Каждый день Лимак ходит из дома в школу и затем возвращается обратно домой. Поскольку Лимак очень легко может заскучать, то он не хочет посещать одну и ту же клетку дважды в течение одного дня, за исключением клетки с его домом, где он начинает и заканчивает свой маршрут. Если Лимак может дойти до школы, а потом вернуться домой не посещая никакую клетку второй раз, то он называет такой день интересным.
Вам требуется последовательно обработать q дней. Для каждого из дней вам требуется проверить является ли он интересным или нет, и соответственно вывести «YES» или «NO» на отдельной строке. Описание следующего дня будет доступно только после того как выведите ответ на текущий и выполните операцию 'flush'.
Гарантируется, что если в некоторый день ни одна клетка поля не является временно заблокированной, то такой день является интересным. Также гарантируется, что клетка, в которой расположен дом Лимака, и клетка, в которой расположена школа никогда не будут заблокированы (ни постоянно, ни временно).
В первой строке входных данных записаны три целых числа h, w и q (2 ≤ h, w ≤ 1000, 1 ≤ q ≤ 10 000) — высота и ширина клетчатого поля, а также количество дней, которые вам следует обработать.
В следующих h строках содержится описание клетчатого поля. В i-й из них записана строка длины w, описывающая i-ю строку поля. Каждый символ строки является либо «.» (соответствует пустой клетке), либо «#» (соответствует постоянно заблокированной клетке). Гарантируется, что если в некоторый день ни одна клетка не будет временно заблокирована, то день будет для Лимака интересным.
Далее следуют описания каждого из q дней. Описание i-го дня начинается со строки, содержащий одно целое число ki (1 ≤ ki ≤ 10) — количества временно заблокированных в этот день клеток. В каждой из последующих ki строк записаны два целых числа ri, j и ci, j (1 ≤ ri, j ≤ h, 1 ≤ ci, j ≤ w), означающих, что временно заблокирована клетка в строке ri, j и столбце ci, j. Гарантируется, что все ki клеток являются различными и ни одна из них не является постоянно заблокированной. Также, ни одна из этих клеток не содержит дом Лимака или школу.
Для каждого из q дней выведите «YES», если данный день является интересным и «NO» в противном случае. После вывода ответа не забудьте вывести символ перевода строки и сделать операцию 'flush', после чего можно будет считать описание следующего дня. Если вы ничего не выведите или забудете сделать операцию 'flush', то можете получить вердикт Idleness Limit Exceeded.
Для сброса буфера вывода (то есть для операции 'flush') сразу после вывода числа или ответа и перевода строки можно сделать:
- fflush(stdout) в языке C++;
- System.out.flush() в Java;
- stdout.flush() в Python;
- flush(output) в Pascal;
- смотрите документацию для других языков.
3 5 4
.....
.....
.#...
1
1 4
1
1 5
2
2 4
3 1
2
1 5
3 3
NO
YES
YES
NO
9 31 5
...............................
...............................
.###.###.#.###...###.###.#.###.
...#.#.#.#.#.......#.#.#.#...#.
.###.#.#.#.###...###.#.#.#...#.
.#...#.#.#.#.#...#...#.#.#...#.
.###.###.#.###...###.###.#...#.
...............................
...............................
5
6 5
2 11
1 14
8 15
2 14
5
2 14
1 14
8 16
6 5
2 11
3
2 2
1 4
8 30
10
3 1
3 11
5 16
7 21
4 16
3 5
7 31
3 9
7 25
3 27
10
3 1
3 9
7 25
3 27
7 21
4 17
3 5
7 31
4 16
3 11
NO
YES
YES
YES
NO
Первый пример состоит из 4 дней. На рисунке ниже показаны возможные маршруты Лимака из дома в школу и обратно для второго и третьего дня (на левом и правом рисунках соответственно). Постоянно заблокированные клетки закрашены красным, а временно заблокированные оранжевым. Чёрные и зелёные стрелочки показывают как Лимак будет идти в школу и обратно соответственно.
Ниже изображено как будет выглядеть поле в каждый из дней второго примера, здесь «#» означает постоянно или временно заблокированную клетку.
