{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eEveryone knows that snakes have hard time living in mazes. Even if a snake lives alone, it can perish by running into a wall or its own tail. A certain participant of snakes competition called Vasya decided to teach his snake to get out from distant areas of the maze. Such sub-mazes are dangerous because the snake has little chance to\r\nget out from them alive, and of course the longer the snake the less chance it has. Vasya trains his snake in the following way: when it\u0027s young and its length is 2, he lets it into a practice dangerous maze. The snake\u0027s goal is to get out from the maze as soon as possible. If the snake survives, then the training will be repeated as soon as the snake reaches the length of 3. The training goes so on until the snake either perishes or matures at the length of 18.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe maze is a rectangle with width \u003ci\u003eW\u003c/i\u003e and length \u003ci\u003eH\u003c/i\u003e, each cell of which is either obstructed \u0027X\u0027 or free \u0027.\u0027. The maze is surrounded with impassable stones \u0027*\u0027 with the exception of the only entrance \u0027#\u0027 located in the border of the maze. Here\u0027s a simple 4-by-3 maze for your reference:\r\n\u003cpre\u003e\r\n***#**\r\n*.X.X*\r\n*.X..*\r\n*....*\r\n******\r\n\u003c/pre\u003e\r\n\r\nThe snake of length \u003ci\u003eL\u003c/i\u003e is a sequence of \u003ci\u003eL\u003c/i\u003e cells. Any two consecutive cells have a common side. All the cells in the sequence are different. The snake can creep in 3 ways relative to its current direction: forward, to the left or to the right. All the cells of snake\u0027s body move at once, each moving into the place of preceding one, except for the head cell. Here are the examples of snake\u0027s movement:\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cpre\u003e321. -\u0026gt; .321\u003c/pre\u003e\u003c/li\u003e\r\n\u003cli\u003e\r\n\u003cpre\u003e\r\n321 -\u0026gt; .32\r\n... ..1\r\n\u003c/pre\u003e\r\n\u003c/li\u003e\r\n\u003cli\u003e\r\n\u003cpre\u003e\r\n12 -\u0026gt; 23\r\n.3 1.\r\n\u003c/pre\u003e\r\n\u003c/li\u003e\r\n\u003cli\u003e\r\n\u003cpre\u003e\r\n12 -\u0026gt; 23\r\n43 14\r\n\u003c/pre\u003e\r\n\u003c/li\u003e\r\n\u003c/ul\u003e\r\nThe snake creeps through exactly one cell per unit of time, or perishes if it has nowhere to creep into.\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 of the input contains \u003ci\u003eH\u003c/i\u003e and \u003ci\u003eW\u003c/i\u003e specifying the size of the maze, where 1 ≤ \u003ci\u003eH\u003c/i\u003e ≤ 300 and 1 ≤ \u003ci\u003eW\u003c/i\u003e ≤ 30. The second line contains \u003ci\u003eh\u003c/i\u003e\u003csub\u003e0\u003c/sub\u003e and \u003ci\u003ew\u003c/i\u003e\u003csub\u003e0\u003c/sub\u003e being the coordinates of the entrance cell; \u003ci\u003eh\u003c/i\u003e\u003csub\u003e0\u003c/sub\u003e equals either 1 or \u003ci\u003eH\u003c/i\u003e, or \u003ci\u003ew\u003c/i\u003e\u003csub\u003e0\u003c/sub\u003e equals either 1 or \u003ci\u003eW\u003c/i\u003e. Following are \u003ci\u003eH\u003c/i\u003e lines of \u003ci\u003eW\u003c/i\u003e characters each, specifying the maze outline (\u0027X\u0027 for obstruction and \u0027.\u0027 for free cell). Time is counted starting from 0; initially the snake has its head at (\u003ci\u003eh\u003c/i\u003e\u003csub\u003e0\u003c/sub\u003e, \u003ci\u003ew\u003c/i\u003e\u003csub\u003e0\u003c/sub\u003e) and all other body cells outside the maze. Time is counted until snake\u0027s head is again at (\u003ci\u003eh\u003c/i\u003e\u003csub\u003e0\u003c/sub\u003e, \u003ci\u003ew\u003c/i\u003e\u003csub\u003e0\u003c/sub\u003e). Even though the maze is a practice one, no snake of length 18 can get out from it alive.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe output must contain 16 lines, where \u003ci\u003ei\u003c/i\u003e\u0027th line is either the best time needed for a snake of length \u003ci\u003ei\u003c/i\u003e+1 to get out from the maze, or −1 if it can\u0027t get out alive.\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\u003e9 9\r\n1 5\r\nXXXX.XXXX\r\nXXX...XXX\r\nXX..X..XX\r\n....XX..X\r\nX.X.X.X.X\r\n..XX.....\r\nX...XXX..\r\nXXXXX....\r\nX.....XXX\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\r\n10\r\n10\r\n22\r\n22\r\n-1\r\n-1\r\n-1\r\n-1\r\n-1\r\n-1\r\n-1\r\n-1\r\n-1\r\n-1\r\n-1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}