Two scouts were sent on a top-secret mission. Unfortunately, they were captured and put in prison.
The plan of the prison is a rectangle divided into square cells with walls parallel to the North-to-South and East-to-West lines. There are doors between some pairs of neighbour cells and walls between the others. Surely, all the outer prison sides are walls — if not, what a sort of prison would it be?
Scouts have to get out of the prison as soon as they could. However, there is an aggravating circumstance: they have been made blind (luckily, only temporarily) by special medicine. Still, both of them have transmitters embedded under their skin, so they could communicate with a base.
The problem is that the scouts didn't know their coordinates relative to the prison. Furthermore, they are unable neither to communicate, nor to see each other, even if occupy the same prison cell.
So the headquaters ordered to proceed as follows: scouts in turn try to move to the neighbour prison cell in one of the four directions (North, South, East or West — what sort of a scout you are if you can't find north with eyes closed!) and report the direction and whether the move was successful or not.
The scouts should be located by their reports and helped to get out. You are given the records of reports of the scouts. Now, determine the minimal number of steps made by scouts after that it becomes possible to determine precisely the coordinates of the scouts.
The first line contains the prison width W and height H, and the number of scouts' reports K (2 ≤ W · H ≤ 150; 1 ≤ K ≤ 105). W is the number of square cells in the direction from East to West, and H — from North to South.
The reports of the scouts are located in the following K lines. Each report consists of two symbols: ("N", "S", "E", "W") — the direction and ("+", "-") — whether the move was successful or not. The odd reports are of the first scout, the even are of the second one.
If a scout makes a successful move, he moves to the destination square. Otherwise, he remains in the same square.
If it is possible to determine the coordinates of both scouts, output "The scouts are safe at step number" and the one-based number of report after which they become known.
If it is impossible to determine the coordinates, output "There is not enough data".
If there are mistakes in the reports (not in the input format), output "A mistake has been made at step number" and the number of first report incompatible with some of the previous ones. Note that you should output this even if there is a mistake after the moment the coordinates are determined.
2 1 4
The scouts are safe at step number 2
2 1 4
There is not enough data
2 1 4
A mistake has been made at step number 4
Источник задачи: SPbSU ITMO contest. Petrozavodsk training camp. Winter 2008.