틱! 택! 토!

틱택토는 3×3 격자에서 두 사람이 번갈아 표시를 그리는 보드게임이다.

규칙은 다음과 같다.

1. 가로줄 2개와 세로줄 2개를 그려 9칸을 만든다.
2. 플레이어 1은 O, 플레이어 2는 X를 빈칸에 번갈아 그린다.
3. 같은 표시 3개가 가로, 세로, 대각선 중 하나로 이어지면 그 플레이어가 이기고 게임이 끝난다.
4. 이어진 줄이 없는 채로 빈칸이 모두 채워지면 무승부로 끝난다.

누구나 쉽게 즐기는 게임이지만, 게임이 이미 끝난 것을 알아채지 못하고 계속 그리는 일이 있다. 그래서 냉정한 심판이 필요하다. 두 플레이어가 번갈아 그린 위치가 순서대로 주어질 때, 승부가 어떻게 결정되는지 판정하는 프로그램을 작성하시오.

첫째 줄에 먼저 시작할 플레이어의 번호가 주어진다. 이 번호는 1 또는 2이다.

다음 9개 줄에 두 플레이어가 번갈아 그린 좌표가 그린 순서대로 주어진다. 각 줄에는 행 번호와 열 번호가 공백으로 구분되어 주어지며, 가장 왼쪽 위 칸이 1 1, 가장 오른쪽 아래 칸이 3 3이다.

같은 칸이 두 번 주어지는 경우는 없으므로 9개 좌표는 9칸을 한 번씩 모두 덮는다. 도중에 승부가 결정되어도 남은 좌표까지 모두 주어지며, 승부가 결정된 뒤에 그린 좌표는 판정에 영향을 주지 않는다.

승부가 결정되는 순간의 승자 번호를 한 줄에 출력한다. 승자 번호는 1 또는 2이다. 9번째 좌표까지 그려도 이어진 줄이 없으면 0을 출력한다.