Magic Compass

Use a magic compass to find a treasure hidden in an $N \times N$ area.

The figure above shows the first sample. When the compass is activated, its red needle points toward the treasure in one of eight directions: up, down, left, right, or one of the four diagonals.

The directions are numbered 1 to 8 clockwise, starting from the top. The coordinates $(x, y)$ denote the cell in the $x$-th row from the top and the $y$-th column from the left. ($x$ and $y$ are integers from 1 to $N$.)

• Direction 1: the treasure has a smaller $x$ coordinate and the same $y$ coordinate.
• Direction 2: the treasure has a smaller $x$ coordinate and a larger $y$ coordinate.
• Direction 3: the treasure has the same $x$ coordinate and a larger $y$ coordinate.
• Direction 4: the treasure has a larger $x$ coordinate and a larger $y$ coordinate.
• Direction 5: the treasure has a larger $x$ coordinate and the same $y$ coordinate.
• Direction 6: the treasure has a larger $x$ coordinate and a smaller $y$ coordinate.
• Direction 7: the treasure has the same $x$ coordinate and a smaller $y$ coordinate.
• Direction 8: the treasure has a smaller $x$ coordinate and a smaller $y$ coordinate.

Using the records of $M$ compass uses, find the location of the treasure. The compass position and the treasure position are always different, and the answer is guaranteed to be unique.

The first line contains two integers $N$ and $M$, separated by a space. ($2 \le N \le 10$, $1 \le M < N^2$)

Each of the next $M$ lines contains $X_i$, $Y_i$, and $K_i$, separated by spaces. These mean that the compass was used at $(X_i, Y_i)$ and the treasure was in direction $K_i$ from that position. ($1 \le X_i, Y_i \le N$, $1 \le K_i \le 8$, all integers)

Print the coordinates of the cell where the treasure is hidden.