Vasya has drawn a square of size n2
on a piece of cross-section paper and divided it into n2
of size n
. Vasya wants to write numbers from 0 to n2
−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 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 ≤ n4. 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, n2−1), the right upper cell is (n2−1, 0), and the right lower cell is (n2−1, n2−1).
0 ≤ с ≤ n2−1.
For any two three-number lines (a1, b1, c1) and (a2, b2, c2) we have either a1 ≠ a2 or b1 ≠ b2.
Output NO if Vasya cannot complete the construction of a magic square. Otherwise, output YES.
0 0 0
1 2 1
2 1 2
3 3 3
Problem Author: Alexander Ipatov
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, January 2006