{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eTwo scouts were sent on a top-secret mission. Unfortunately, they were captured and put in prison.\r\n\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe 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\u0026nbsp;— if not, what a sort of prison would it be?\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eScouts 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.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe problem is that the scouts didn\u0027t 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.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eSo 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\u0026nbsp;— what sort of a scout you are if you can\u0027t find north with eyes closed!) and report the direction and whether the move was successful or not.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe 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.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe first line contains the prison width \u003ci\u003eW\u003c/i\u003e and height \u003ci\u003eH\u003c/i\u003e, and the number of scouts\u0027 reports \u003ci\u003eK\u003c/i\u003e (\u003cnobr\u003e2 ≤ \u003ci\u003eW\u003c/i\u003e · \u003ci\u003eH\u003c/i\u003e ≤ 150;\u003c/nobr\u003e \u003cnobr\u003e1 ≤ \u003ci\u003eK\u003c/i\u003e ≤ 10\u003csup\u003e5\u003c/sup\u003e\u003c/nobr\u003e). \u003ci\u003eW\u003c/i\u003e\u0026nbsp;is the number of square cells in the direction from East to West, and \u003ci\u003eH\u003c/i\u003e\u0026nbsp;— from North to South.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe reports of the scouts are located in the following \u003ci\u003eK\u003c/i\u003e lines. Each report consists of two symbols: (\"N\", \"S\", \"E\", \"W\")\u0026nbsp;— the direction and (\"+\", \"-\")\u0026nbsp;— whether the move was successful or not. The odd reports are of the first scout, the even are of the second one.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eIf a scout makes a successful move, he moves to the destination square. Otherwise, he remains in the same square.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eIf 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.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eIf it is impossible to determine the coordinates, output \"There is not enough data\".\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eIf 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.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 1 4\r\nE+\r\nW-\r\nN-\r\nS-\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eThe scouts are safe at step number 2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr\u003e\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 1 4\r\nN-\r\nW-\r\nN-\r\nS-\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eThere is not enough data\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr\u003e\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 1 4\r\nN-\r\nW-\r\nN-\r\nS+\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eA mistake has been made at step number 4\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}