ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1338. Automobiles

Time limit: 3.0 second
Memory limit: 64 MB
Everyone knows what traffic congestion is. Even supercomputer won’t be able to lay an optimal passage of the city center in the rush-hours. But it is possible to simulate the traffic flows.
For that the following experiment is carried out. We choose several check points on the streets net of the city and one goal T from the checkpoints. We send a car from each checkpoint (except T) to the point T along the shortest way. In the point T we fix how many cars came from the North, how many from the South, from the East and from the West. So we can judge about the functioning capacity of the approaches to the point T.
You are to carry out such an experiment. No, you are not given a car! You are no to go anywhere. You are only to write a program simulating the experiment.

Input

Input contains the city plan description in the following format. The first line contains two integers W and H (1 ≤ W, H ≤ 500) – the width and the height of the plan. The next H lines consists of the streets net and checkpoints description. A symbol “.” means a place where a building is. A symbol “#” means a road fragment. A symbol “o” (small Latin letter) means a checkpoint. A road fragment always occupy a cell completely. Two road fragments belong to one road if and only if they have a common side.
Then there is a series of assignments of the experiment. First of all there is a number of assignments M (0 ≤ M ≤ 20). Each of the next M lines contains the number of the goal point T for the corresponding experiment. Assume that the checkpoints are numbered bottom-up and from left to right.
If some car is to choose a way from several shortest ones the next scheme of priorities acts: South, North, West, East.

Output

You are to output the results of each experiment in the following format:
Experiment #N: North: Rn, South: Rs, East: Re, West: Rw
where Rn, Rs, Re and Rw - an amount of cars that came in the experiment number N to the goal point from the North, South, East and West respectively.

Sample

inputoutput
10 5
..####....
..o..o....
..####.#o.
......##..
.o#####...
1
4
Experiment #1: North: 0, South: 1, East: 0, West: 0
Problem Author: Alexander Klepinin
Problem Source: USU Championship 2004