С пробками на дорогах все знакомы не понаслышке. Проложить оптимальный маршрут проезда через центр города, перегруженный в час пик, не сможет, пожалуй, даже суперкомпьютер. Но вот смоделировать потоки транспорта вполне под силу.

Для этого производится следующий эксперимент. На сетке улиц города выбираются несколько контрольных точек. Среди контрольных точек выбирается одна целевая точка T. И изо всех контрольных точек (кроме T) в точку T по кратчайшему маршруту отправляется по одной машине. В целевой же точке фиксируется, сколько машин прибыло в эту точку с севера, сколько с юга, сколько с запада и сколько с востока. Соответственно, можно судить о загруженности подъездов к целевой точке.

Вам предлагается провести такой эксперимент. Нет, машины Вам не полагается. И ехать никуда не нужно. Нужно всего лишь написать программу, моделирующую описанный эксперимент.

Ввод содержит описание плана города в следующем формате. В первой строчке находятся два целых числа W и H (1 ≤ W, H ≤ 500), ширина и высота плана. В следующих H строках описывается сетка улиц и контрольные точки. Символом ‘.’ обозначается место, занятое зданиями. Символом ‘#’ обозначаются фрагменты дорог. Символом ‘o’ (строчная латинская) обозначаются контрольные точки. Фрагмент дороги всегда занимает ячейку плана полностью. Два элемента дороги относятся к одной дороге только в том случае, когда имеют общую сторону.

После описания плана города следует серия заданий на моделирование эксперимента. Сначала указывается количество заданий M (0 ≤ M ≤ 20), а в каждой из последующих M строчек задается номер целевой точки T для соответствующего эксперимента. Предполагается, что контрольные точки на плане перенумерованы снизу вверх и слева направо.

Если оказывается, что какая-то машина должна выбирать дальнейший маршрут из нескольких кратчайших, действует следующая схема приоритетов на дальнейшее движение: юг, север, запад, восток.

Выведите результат для каждого из экспериментов в следующем формате:

где Rn, Rs, Re и Rw – количество машин, прибывшее в эксперименте с номером N в целевую точку с севера, юга, востока и запада соответственно.