Острова

Имеется прямоугольная карта островов размера N×M. Вся область разделена на квадратные ячейки. Каждая ячейка либо заполнена водой, либо является сушей. В некоторых ячейках находятся люди (не более одного в ячейке). Люди могут передвигаться в соседние по стороне ячейки, являющиеся сушей. Вода постепенно уходит. То есть на месте воды каждую минуту появляется 1 участок суши. Ваша задача на каждом шаге определять, сколько пар людей могут добраться друг до друга по суше.

Формат входного файла

В первой строке входного файла содержатся  2 целых числа N и M (1 ≤ N, M ≤ 1000).

Следующие N строк содержат по M символов каждая. Символ «w»  обозначает воду, «g» - сушу, «p» - человека на суше

Далее следует число K (0 ≤ K ≤ 10⁵) – количество минут. В следующих К строках содержатся пары чисел X_i (0 ≤ X_i < N) и Y_i (0 ≤ Y_i < M)  координаты нового участка суши. Левая верхняя ячейка имеет координату (0, 0)

Формат выходного файла

Выведите в выходной файл K целых чисел по одному в каждой строке.

Пример

После появления суши друг до друга смогут добраться пары:

(0,1) и (1,1)

(0,1) и (1,2)

(1,1) и (1,2)