28016번 - 경품 추첨

못과 빈칸으로 이루어진 $N\times M$ 크기의 추첨 판에서 경품 추첨을 진행하려고 한다. 추첨이 진행되는 과정은 다음과 같다.

1. 추첨 판 임의의 위치에 한 칸 크기의 못들이 설치된다.
2. 추첨 판의 가장 위 행 중 한 칸에서 공 하나가 떨어진다.
3. 공은 아래쪽으로 직진하며 떨어지지만, 못을 만나면 같은 확률로 못 양옆 중 한 곳에 떨어진다.
4. 공이 떨어지다 못을 만난 경우, 공의 옆이나 대각선 아래에 못이 있다면 그 방향으로 지나가지 못하고 걸린다. 이때는 공을 처음 위치로 되돌려 추첨을 다시 진행한다.
5. 가장 아래 행에 도착한 공의 열 번호가 당첨 번호가 된다.

못이 박힌 후에 추첨 번호를 선택한다고 할 때, 당첨될 확률이 가장 높은 번호를 알아내 보자.

첫째 줄에 추첨 판의 세로 길이 $N$과 가로 길이 $M$이 공백으로 구분되어 주어진다. $(3\leq N,M\leq 100)$

둘째 줄부터 $N$개의 줄에 추첨 판을 나타내는 $M$개의 정수가 공백으로 구분되어 주어진다. '0'은 빈 공간, '1'은 못, '2'는 처음 공의 위치를 의미한다.

처음 공의 위치는 반드시 가장 위 행에 하나 존재한다.

가장 왼쪽 열과 가장 오른쪽 열에는 못이 설치되지 않는다.

가장 당첨될 확률이 높은 번호 $C$를 출력한다. 그런 번호가 여러 개라면 그중 가장 작은 번호를 출력한다. 모든 번호가 당첨될 확률이 없다면 '-1'을 출력한다. $(0\leq C\leq M-1)$