Верблюд#8723

Верблюд

0,45 секунди

256 мегабайтів

Дуже складна

Давайте розглянемо нову шахову фігуру, яку назвемо "верблюд-тон". Ця фігура рухається стрибками: горизонтально або вертикально — через дві клітинки шахівниці, або по діагоналі — через одну клітинку. На малюнку зображено частину дошки з верблюдом-тоном, розташованим у центрі, та позиції (позначені x), куди він може переміститися за один хід. Звісно, він не може виходити за межі ігрової дошки, яка є великим квадратом, поділеним на $N \times N$ N \times N маленьких квадратів. У цій задачі $N$ завжди ділиться на $5$ .

Верблюд-тон починає з клітинки у верхньому лівому куті дошки. Завдання полягає в тому, щоб зробити послідовність ходів на дошці, відвідуючи кожну клітинку рівно один раз. Крім того, після $N^{2} - 1$ N^2-1 ходу фігура повинна бути на відстані одного ходу від своєї початкової позиції. Це так званий "верблюд-тоніанський цикл"!

Напишіть програму camel, щоб знайти будь-який можливий спосіб зіграти гру, або повідомити, що цикл є неможливим.

Вхідні дані

Зі стандартного вводу читається один рядок, що містить лише одне ціле число $N$ ( $2 \leq N \leq 1000$ 2 \leq N \leq 1000). $N$ завжди ділиться на $5$ .

Вихідні дані

Програма повинна вивести на стандартний вихід: один рядок з повідомленням NO, якщо ви встановите, що цикл неможливий, або $N$ рядків, кожен з яких містить $N$ розділених пробілами чисел, які є різними додатними цілими числами від $1$ до $N^{2}$ N^2 включно. Перше число в першому рядку — $1$ . Вихід представляє ігрову дошку ( $N \times N$ N \times N квадратів), де цілі числа вказують на послідовні зайняті позиції.

Приклади

Приклад 1

Примітка

Верблюд-тон починає з верхньої лівої позиції (ряд:1, стовпець:1), пронумерованої $1$ . Друга зайнята позиція — (ряд:4, стовпець:1), тому вона пронумерована $2$ . Наступна позиція — (ряд:7, стовпець:1), і вона пронумерована $3$ , і так далі. Остання (сота) зайнята позиція — (ряд:3, стовпець:3), і вона знаходиться на відстані одного ходу від початкової позиції.