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?

#### Input Specification

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 .

#### Output Specification

A single integer; the number of blocks Ruby needs to place.

#### Sample Input 1

```
5 2
..#..
.....
```

#### Sample Output 1

`1`

#### Explanation

Ruby may place a block at to block all of Yang's possible routes.

#### Sample Input 2

```
5 1
.....
```

#### Sample Output 2

`1`

#### Explanation

Placing any block will make the game unwinnable.

#### Sample Input 3

```
3 3
.#.
.##
..#
```

#### Sample Output 3

`1`

#### Sample Input 4

```
5 5
..#..
#....
.#..#
#..##
.##..
```

#### Sample Output 4

`1`

#### Explanation

A block must be placed at to prevent Yang from ever being able to finish.

## Comments

Sorry, just some more confirmations:

Is the piece allowed to go off the bottom and enter from the top (clarifying since technically a block does not do that move, rather off the top and enter from the bottom)?

Is this allowed:

Time t

R

#

Time t+1

#

R

Can it go through the block?

Edit: Answers to both questions are yes

Is Sample Input 4 correct?

Even if you place a block at (1,0), you can start at the topmost leftmost tile and move "Right Right Stay Right Right".

Am I reading the problem wrong? Thank you!

If there is a block at (1,0), you cannot start at the top-left tile and move right, because you would then encounter said block.

But don't the blocks move up 1 unit every second so that at t=1, the said block is at (1,N-1) and the player is at (1,0)?

To move a piece when , the adjacent cell must be empty at , not after the rotation at .

"A player may move their piece to a tile at time if and only if is clear…at ."

So just confirming, the following case is allowed:

But this case is not:

Also, it seems that in the simulation of the game, state t=9 to t=10 matches the latter case.

Thank you!

Scratch what I said earlier. After reviewing the simulation, I have come to the conclusion that I have no idea how any of this works.

It seems like any move is allowed as long as the destination tile will be clear

after the next shift.But then that would contradict sample 4.

I believe the correct square to be blocked is (3, 4), but could someone else confirm?

I believe that there is still a path if is blocked.

(3, 4) would be:

Indices start from 0.

Oops, my bad. Can confirm, one block at makes the game unwinnable.

https://dmoj.ca/problem/helloworld#comment-5742

Is this excluding the red block?

EDIT: Seems so.

Sample 1 explanation is still wrong

Sorry for the inconvenience.

Samples are incorrect