|
Имеется прямоугольная карта островов размера N×M. Вся область
разделена на квадратные ячейки. Каждая ячейка либо заполнена водой, либо
является сушей. В некоторых ячейках находятся люди (не более одного в ячейке).
Люди могут передвигаться в соседние по стороне ячейки, являющиеся сушей. Вода
постепенно уходит. То есть на месте воды каждую минуту появляется 1 участок
суши. Ваша задача на каждом шаге определять, сколько пар людей могут добраться
друг до друга по суше.
Формат входного файла
В первой строке входного файла содержатся 2 целых числа N и M (1 ≤ N, M ≤ 1000).
Следующие N строк содержат по M символов каждая. Символ «w»
обозначает воду, «g» - сушу, «p»
- человека на суше
Далее следует число K (0 ≤ K ≤ 105)
– количество минут. В следующих К строках содержатся пары чисел Xi (0 ≤ Xi < N)
и Yi (0 ≤ Yi < M)
координаты нового участка суши. Левая верхняя ячейка имеет координату (0, 0)
Формат выходного файла
Выведите в выходной файл K
целых чисел по одному в каждой строке.
Пример
|
Входные данные
|
Выходные данные
|
|
2 3
pwg
wpp
1
0 1
|
3
|
После появления суши друг до друга смогут добраться пары:
(0,1) и (1,1)
(0,1) и (1,2)
(1,1) и (1,2)
|
