Problem D
Island Infection

The world of sample input 4.

The world consists of $R$ rows, each of length $C$. Each position is 0 (“water”), 1 (“land”), 2 (“virus”), or 3 (“human”). The virus spreads in the obvious fashion to non-water positions with a shared border. For instance, here is the development in a small world with $R=1$ and $C=10$:

Note that the process stops here, and the human will never be infected.

Here are a few rounds of development in a world with $R=4$ and $C=6$:

111001    112001    122001    222001 
112000    122000    222000    222000 
011103 -> 012103 -> 022203 -> 022203 
101111    101111    102111    102211

The process will continue beyond these 4 rounds, and you can convince yourself that the human will eventually be infected.

More precisely, a tile position marked 1 or 3 turns into a 2 in round $i$ (we call that “getting infected”) exactly if any of the at most 4 adjacent tiles (to the north, south, east, or west) contains a 2 in round $i-1$. Note that infections don’t spread “diagonally across corners”, as shown in the bottom left position in the larger example. No position ever changes back from 2, and no water position ever changes.

The goal is to determine if the human gets infected.

Input

Input begins with $R$ and $C$ on the first line, followed by $R$ lines of $C$ symbols describing the starting world. There is exactly one 2 and exactly one 3 in the last $R$ lines.

Output

The output is a single line containing the integer 1 if the human will get infected, 0 otherwise.

Test groups

1 2
23

1

2 2
02
30

0

1 10
0101211030

0

4 6
111001
112000
011103
101111

1