cho.sh

Tic! Tac! Toe!

Given the first player and the nine moves in order, report the player who first completes a row, column, or diagonal, or 0 for a draw.

Easy3SimulationImplementationBrute forceInterviewNo attempts yetTime limit1sMemory limit128 MB

Problem

Tic-tac-toe is a board game in which two people take turns marking cells of a 3×3 grid.

A tic-tac-toe grid

The rules are these.

  1. Draw two horizontal lines and two vertical lines to make 9 cells.
  2. Player 1 draws O and player 2 draws X, taking turns on empty cells.
  3. As soon as one player has three marks in a row, in a column, or on a diagonal, that player wins and the game ends.
  4. If every cell is filled and no such line exists, the game ends in a draw.

The game is easy, but players sometimes miss the moment it ended and keep drawing. A cold referee is needed. Given the positions the two players marked in order, decide how the game is settled.

Input

The first line has the number of the player who moves first. That number is 1 or 2.

Each of the next 9 lines has one coordinate, in the order the marks were drawn. A line holds a row number and a column number separated by a space. The top left cell is 1 1 and the bottom right cell is 3 3.

No cell is given twice, so the 9 coordinates cover all 9 cells once each. The remaining coordinates are given even when the game is already settled, and coordinates drawn after that moment do not affect the verdict.

Output

Print, on one line, the number of the player who wins at the moment the game is settled. That number is 1 or 2. If no line is formed after all 9 coordinates, print 0.