Вася нарисовал на листке бумаги в клетку квадрат размера n² × n² и разделил его на n² малых квадратов размера n × n. Вася хочет расставить в клетках числа от 0 до n²−1, чтобы получить магический квадрат. А именно, магическим квадратом он называет такой квадрат, что:

1. В левой верхней клетке стоит число 0.
2. В любом столбце никакие два числа не повторяются.
3. В любой строке никакие два числа не повторяются.
4. В любом малом квадрате никакие два числа не повторяются.
5. Если поменять местами два малых квадрата, имеющих общую сторону, то получится квадрат, удовлетворяющий свойствам 2-4.

Несколько чисел Вася уже расставил. Скажите, сможет ли он, не стирая этих чисел, дополнить квадрат до магического.

В первой строке — целые числа 1 ≤ n ≤ 3 и 0 ≤ k ≤ n⁴. В каждой из следующих k строк — тройка чисел a, b, c, означающая, что Вася поставил в клетке с номером (a, b) число c. Левая верхняя клетка имеет номер (0, 0), левая нижняя (0, n²−1), правая верхняя (n²−1, 0), правая нижняя (n²−1, n²−1). 0 ≤ с ≤ n²−1. Для любых двух троек чисел (a₁, b₁, c₁) и (a₂, b₂, c₂) либо a₁ ≠ a₂, либо b₁ ≠ b₂.

Выведите NO, если Вася не сможет достроить квадрат до магического. В противном случае выведите YES.