Vasya has drawn a square of size
n^{2} ×
n^{2} on a piece of crosssection paper and divided it into
n^{2} smaller squares
of size
n ×
n. Vasya wants to write numbers from 0 to
n^{2}−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:
 There is zero in the left upper cell.
 There are no repeating numbers in any column.
 There are no repeating numbers in any row.
 There are no repeating numbers in any of the smaller squares.
 If we swap two smaller squares having a common side, then we obtain a square satisfying properties 24.
Vasya has already written several numbers.
Determine if it is possible to fill the remaining cells and obtain a magic square.
Input
The first line contains integers 1 ≤ n ≤ 3 and 0 ≤ k ≤ n^{4}. 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^{2}−1), the right upper cell is (n^{2}−1, 0), and the right lower cell is (n^{2}−1, n^{2}−1).
0 ≤ с ≤ n^{2}−1.
For any two threenumber lines (a_{1}, b_{1}, c_{1}) and (a_{2}, b_{2}, c_{2}) we have either a_{1} ≠ a_{2} or b_{1} ≠ b_{2}.
Output
Output NO if Vasya cannot complete the construction of a magic square. Otherwise, output YES.
Samples
input  output 

2 4
0 0 0
1 2 1
2 1 2
3 3 3
 NO

2 0
 YES

Problem Author: Alexander Ipatov
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, January 2006