Ruby and her sister Yang are playing with a mechanized board game.
The board consists of square cells of unit dimensions on a plane, with the origin defined as the topmost left tile. Some of these cells are originally colored black, signifying an impassible block.
Every second, the board moves every block up unit, and wraps them around to . That is, a tile located at at will be at when , and when .
A player may start the game by placing a red piece on any clear tile where . A player may move their piece to a tile at time if and only if is clear (i.e., does not contain a wall) at . Likewise, the starting position must be clear at .
Every second, the player may move their red piece by at most unit every second in cardinal directions, with the player's piece wrapping around the board like wall blocks do. A player may keep their piece stationary at time so long as their current position is not covered by a wall at .
The goal of the player is to have their block reach .
Ruby is playing Yang. Since they recently argued over something petty, Ruby wants to get back at Yang by making the game impossible for Yang to finish. To this end, she will be placing — while Yang is not looking — a number of new wall blocks to cut off Yang's movement. How many blocks does she need, if she wants to use as few as possible to make the game unwinnable?
The first line of input will contain two space-separated integers and .
The next lines will each contain characters, with
. representing a blank space and
# representing a block at .
A single integer; the number of blocks Ruby needs to place.
Sample Input 1
5 2 ..#.. .....
Sample Output 1
Ruby may place a block at to block all of Yang's possible routes.
Sample Input 2
5 1 .....
Sample Output 2
Placing any block will make the game unwinnable.
Sample Input 3
3 3 .#. .## ..#
Sample Output 3
Sample Input 4
5 5 ..#.. #.... .#..# #..## .##..
Sample Output 4
A block must be placed at to prevent Yang from ever being able to finish.