깃털

비트란디야(Bitlandija)는 직사각형 모양의 큰 섬으로, $N \times K$개의 단위 정사각형(칸)으로 나뉘어 있습니다.

각 칸은 바위이거나 평지입니다. 평지 칸에는 바람이 있을 수도, 없을 수도 있습니다. 바람은 두 종류입니다.

• 일정한 바람: 네 방향(북, 동, 남, 서) 중 한 방향으로 $1$ m/s의 속도로 불며, 방향이 바뀌지 않습니다.
• 회오리바람: 마찬가지로 $1$ m/s로 불지만, 매 초마다 방향이 시계 방향으로 한 단계씩 바뀝니다(북 $\to$ 동 $\to$ 남 $\to$ 서 $\to$ 북). 깃털을 잃어버린 순간($0$초)에 각 회오리바람은 자신의 초기 방향을 향합니다.

비트란디야의 유명한 참새 Passer domesticus가 깃털 하나를 잃어버렸습니다. 깃털이 지금 있는 칸은 알고 있으며, 깃털이 결국 어떻게 될지 알고 싶어 합니다. 매 초 깃털은 현재 있는 칸의 바람에 의해 움직입니다.

• 바람이 이웃한 평지 칸 쪽으로 불면, 깃털은 그 이웃 칸으로 이동합니다.
• 바람이 이웃한 바위 칸 쪽으로 불면, 깃털은 그 자리에 매달린 채 움직이지 않습니다.
• 바람이 섬의 가장자리 바깥으로 불면, 깃털은 섬 밖으로 날아갑니다.
• 깃털이 바람이 없는 평지 칸에 있으면 아무것도 밀지 않으므로, 깃털은 그 자리에 내려앉습니다.

깃털의 시작 칸이 주어질 때, 깃털의 운명을 판정하세요.

1. 절대 내려앉지 않는가?
2. 언젠가 내려앉는가? 그렇다면 어느 칸인가?
3. 섬 밖으로 날아가는가? 그렇다면 마지막으로 머문 섬의 칸은 어디인가?

첫째 줄에 섬의 너비 $N$과 길이 $K$가 주어집니다.

이어지는 $K$개의 줄에는 각각 $N$개의 정수가 주어지며, 섬의 각 칸을 나타냅니다.

• $0$ — 바람이 없는 평지 칸.
• $1$ — 북쪽으로 부는 일정한 바람이 있는 평지 칸.
• $2$ — 동쪽으로 부는 일정한 바람이 있는 평지 칸.
• $3$ — 남쪽으로 부는 일정한 바람이 있는 평지 칸.
• $4$ — 서쪽으로 부는 일정한 바람이 있는 평지 칸.
• $5$ — 초기 방향이 북인 회오리바람이 있는 평지 칸.
• $6$ — 초기 방향이 동인 회오리바람이 있는 평지 칸.
• $7$ — 초기 방향이 남인 회오리바람이 있는 평지 칸.
• $8$ — 초기 방향이 서인 회오리바람이 있는 평지 칸.
• $9$ — 바위.

마지막 줄에는 두 정수 $x$와 $y$가 주어지며, 깃털의 시작 좌표입니다($1 \le x \le N$, $1 \le y \le K$). 시작 칸은 절대 바위가 아닙니다.

중요: 섬 지도는 좌표 $y$가 감소하는 순서, 즉 $y = K, K-1, \ldots, 1$로 주어집니다. 각 줄 안에서 값은 $x = 1, 2, \ldots, N$의 순서로 왼쪽에서 오른쪽으로 주어집니다. 섬의 왼쪽 아래 칸은 좌표 $(1, 1)$이며 남서쪽에 있고, 오른쪽 위 칸은 좌표 $(N, K)$이며 북동쪽에 있습니다.

다음 형식으로 답을 출력하세요.

1. 깃털이 절대 내려앉지 않으면, 숫자 $0$을 출력합니다.
2. 깃털이 멈추어 내려앉으면, 첫째 줄에 $1$을, 둘째 줄에 내려앉은 칸의 좌표 $x_1\ y_1$을 출력합니다.
3. 깃털이 섬 밖으로 날아가면, 첫째 줄에 $2$를, 둘째 줄에 마지막으로 머문 섬의 칸의 좌표 $x_2\ y_2$를 출력합니다.

• $1 \le N, K \le 1000$