Hexodoku#6741

Hexodoku

4 секунди

256 мегабайтів

Легка

Судоку — це захоплююча гра, яка приносить задоволення багатьом людям. Існує легенда, що видатний програміст витратив лише $7$ хвилин на створення програми для розв'язання стандартного судоку. Це вражає, чи не так? Тепер він вирішив іншу задачу. Чи зможете ви повторити його успіх?

Розгляньте нестандартну шестикутну дошку Судоку:

Клітини на дошці пронумеровані від $1$ до $31$ .

Згідно з правилами, числа (від $1$ до $K$ ) можуть бути розміщені в клітинах так, щоб усі числа в одному рядку (рядки розташовані в трьох напрямках) були різними.

Крім того, для кожної з позначених клітин число в цій клітині та всі числа в сусідніх клітинах також повинні бути різними.

Числа повинні бути різними

Деякі числа можуть вже бути розміщені в клітинах згідно з правилами. Вам потрібно знайти $N$ -те розв'язання в лексикографічному порядку, якщо воно існує.

Нехай $A_{i}$ A_i — це число в клітині $i$ в розв'язанні $A$ , а $B_{i}$ B_i — число в клітині $i$ в розв'язанні $B$ . Розв'язання $A$ є лексикографічно меншим за розв'язання $B$ , якщо існує таке $j$ , що для кожного $i$ , де $i < j$ i < j: $A_{i} = B_{i}$ A_i = B_i і $A_{j} < B_{j}$ A_j < B_j.

Вхідні дані

Перша строка вхідних даних містить два цілі числа $K$ та $N$ .

$7 \leq K \leq 31$ 7 \le K \le 31
$1 \leq N \leq 100000$ 1 \le N \le 100000

Друга строка містить $31$ ціле число: $A_{i}$ A_i ( $1 \leq i \leq 31$ 1 \le i \le 31) — це число, що стоїть у клітині $i$ .

$1 \leq A_{i} \leq K$ 1 \le A_i \le K, або $0$ , якщо в цій клітині немає числа.

Вихідні дані

Перша строка вихідних даних повинна містити відповідь:

"Found" — якщо розв'язання знайдено.
"No way" — якщо немає $N$ -го розв'язання.

Якщо розв'язання знайдено, друга строка вихідних даних повинна містити $N$ -те розв'язання у тому ж форматі, що й у вхідних даних.

Це перший приклад вище:

Приклади

Приклад 1