Everyone 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 get 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's young and its length is 2, he lets it into a practice dangerous maze. The snake's 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.

The maze is a rectangle with width W and length H, each cell of which is either obstructed 'X' or free '.'. The maze is surrounded with impassable stones '*' with the exception of the only entrance '#' located in the border of the maze. Here's a simple 4-by-3 maze for your reference:

***#**
*.X.X*
*.X..*
*....*
******

The snake of length L is a sequence of L 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's body move at once, each moving into the place of preceding one, except for the head cell. Here are the examples of snake's movement:

• 321. -> .321

• 321 -> .32
  ...    ..1
  

• 12 -> 23
  .3    1.
  

• 12 -> 23
  43    14
  

The snake creeps through exactly one cell per unit of time, or perishes if it has nowhere to creep into.

The first line of the input contains H and W specifying the size of the maze, where 1 ≤ H ≤ 300 and 1 ≤ W ≤ 30. The second line contains h₀ and w₀ being the coordinates of the entrance cell; h₀ equals either 1 or H, or w₀ equals either 1 or W. Following are H lines of W characters each, specifying the maze outline ('X' for obstruction and '.' for free cell). Time is counted starting from 0; initially the snake has its head at (h₀, w₀) and all other body cells outside the maze. Time is counted until snake's head is again at (h₀, w₀). Even though the maze is a practice one, no snake of length 18 can get out from it alive.

The output must contain 16 lines, where i'th line is either the best time needed for a snake of length i+1 to get out from the maze, or −1 if it can't get out alive.