Dice Grid
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дебора играет в видеоигру. На одном из уровней ей дается куб и плоская разноцветная сетка из $$$n \times n$$$ ячеек. Ячейка в строке $$$i$$$ и столбце $$$j$$$ обозначается $$$(i, j)$$$ и имеет цвет $$$c_{i, j}$$$. Дебора видет всю сетку, включая цвет каждой ячейки.

Размер грани куба соответствует размеру ячейки сетки. Всякий раз, когда мы говорим, что куб находится в ячейке $$$(i, j)$$$, это означает, что его нижняя грань совпадает с ячейкой сетки $$$(i, j)$$$. Напротив нижней грани находится верхняя грань. Грань, "смотрящая" на ячейку $$$(i + 1, j)$$$, называется лицевой гранью. Задняя грань "смотрит" на ячейку $$$(i - 1, j)$$$, правая грань "смотрит" на ячейку $$$(i, j + 1)$$$, а левая грань "смотрит" на ячейку $$$(i, j - 1)$$$.

Изначально куб находится в ячейке $$$(1, 1)$$$. Цель игры — перекатить кубик в ячейку $$$(n, n)$$$.

Из любой ячейки $$$(i, j)$$$ Дебора может переместить куб только вниз — в ячейку $$$(i + 1, j)$$$ или вправо — в ячейку $$$(i, j + 1) $$$. Способ перемещения куба вниз состоит в том, чтобы вращать его вокруг ребра, соединяющего его нижнюю и переднюю грани. Например, после поворота передняя грань становится новой нижней гранью. Точно так же способ переместить куб вправо состоит в том, чтобы вращать его вокруг ребра, соединяющего его нижнюю и правую грани.

Грани куба еще не окрашены. Дебора должна раскрасить каждую сторону в любой цвет, который она хочет. В каждый момент игры, включая моменты, когда куб находится в точках $$$(1, 1)$$$ и $$$(n, n)$$$, цвет нижней грани куба должен совпадать с цветом ячейки сетки, в которой находится куб.

Цель состоит в том, чтобы покрасить куб таким образом, чтобы Дебора смогла переместить куб из ячейки $$$(1, 1)$$$ в ячейку $$$(n, n)$$$, удовлетворяя указанным выше условиям. Найдите любую возможную раскраску куба.

Входные данные

Каждый тест содержит несколько тестовых случаев. Первая строка содержит количество тестов $$$t$$$ ($$$1 \le t \le 625$$$). Далее следует описание тестовых случаев.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ — количество строк и столбцов в сетке ($$$2 \le n \le 50$$$).

$$$i$$$-я из следующих $$$n$$$ строк содержит $$$n$$$ целых чисел $$$c_{i, 1}, c_{i, 2}, \ldots, c_{i, n}$$$ ($$$0 \le c_{i , j} < 2^{24}$$$). Цвет ячейки $$$(i, j)$$$ в RGB равен $$$c_{i, j}$$$.

Гарантируется, что сумма $$$n^2$$$ по всем тестам не превышает $$$2500$$$.

Выходные данные

Для каждого набора входных данных, если раскраски не существует, выведите одно слово "No" на отдельной строке.

В противном случае в первой строке выведите одно слово "Yes".

Во второй строке выведите шесть целых чисел $$$a_b$$$, $$$a_l$$$, $$$a_k$$$, $$$a_f$$$, $$$a_r$$$ и $$$a_t$$$ — цвета нижней, левой, задней, передней, правой, и верхней грани куба соответственно в исходном положении в ячейке $$$(1, 1)$$$ ($$$0 \le a_i < 2^{24}$$$).

Если существует несколько возможных раскрасок, выведите любую из них.

Пример

Входные данные

    421 10 031 2 39 6 47 8 141 2 3 49 8 7 510 8 12 213 14 15 641 2 3 45 6 7 89 10 11 1213 14 15 16

Выходные данные

    Yes
    1 3 4 0 0 5
    Yes
    1 10 10 4 2 3
    Yes
    1 4 6 5 2 3
    No

Примечание

В третьем тестовом примере куб можно переместить из $$$(1, 1)$$$ в $$$(4, 4)$$$ со следующей последовательностью ходов: вправо, вправо, вправо, вниз, вниз и вниз.