ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1466. Magic Square

Time limit: 1.0 second
Memory limit: 64 MB
Vasya has drawn a square of size n2 × n2 on a piece of cross-section paper and divided it into n2 smaller squares of size n × 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:
  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 ≤ kn4. 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 a1a2 or b1b2.


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


2 4
0 0 0
1 2 1
2 1 2
3 3 3
2 0
Problem Author: Alexander Ipatov
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, January 2006