Vasya has drawn a square of size n² × n² on a piece of cross-section paper and divided it into n² smaller squares of size n × n. Vasya wants to write numbers from 0 to n²−1 in the squares of the paper (let's call them cells) in order to obtain a magic square. Namely, a magic square is a square in which:

1. There is zero in the left upper cell.
2. There are no repeating numbers in any column.
3. There are no repeating numbers in any row.
4. There are no repeating numbers in any of the smaller squares.
5. If we swap two smaller squares having a common side, then we obtain a square satisfying properties 2-4.

Vasya has already written several numbers. Determine if it is possible to fill the remaining cells and obtain a magic square.

The first line contains integers 1 ≤ n ≤ 3 and 0 ≤ k ≤ n⁴. Each of the next k lines contains three numbers a, b, c, which mean that Vasya has written the number c in the cell (a, b). The left upper cell has coordinates (0, 0), the left lower cell is (0, n²−1), the right upper cell is (n²−1, 0), and the right lower cell is (n²−1, n²−1). 0 ≤ с ≤ n²−1. For any two three-number lines (a₁, b₁, c₁) and (a₂, b₂, c₂) we have either a₁ ≠ a₂ or b₁ ≠ b₂.

Output NO if Vasya cannot complete the construction of a magic square. Otherwise, output YES.