437. Hexodoku
Time limit per test: 4
second(s)
Memory limit: 262144
kilobytes
input: standard
output: standard
Sudoku is an amazing game. Many people have fun solving it. They say that a legendary programmer had spent just 7 minutes on writing a program that solves standard sudoku. That's über cool, don't you think? And now he has solved another problem. Can you do the same?
Consider a nonstandard hexagonal Sudoku board:
The cells are numbered from 1 to 31.
According to the rules, numbers (from 1 to
K) can be placed in the cells with the condition that all numbers in the same row (rows are located in three directions) must be different.
Additionally, for each of the marked cells, the number in marked cell and all numbers in adjacent cells must also differ from each other.
Some numbers may already be placed in the cells according to the rules. You are to find
Nth solution in lexicographical order, if it exists.
Let
A_{i} be the number in the cell
i in solution
A, and
B_{i} — the number in the cell
i in solution
B. Solution
A is lexicographically smaller than solution
B, if such
j exists that for each
i where
i <
j:
A_{i} =
B_{i} and
A_{j} <
B_{j}.
Input
First line of input contains two integers
K and
N.
 7 ≤ K ≤ 31

Second line contains 31 integer numbers:
A_{i} (1 ≤
i ≤ 31) is the number standing in the cell
i.
 1 ≤ A_{i} ≤ K, or 0, if there is no number in this cell.
Output
First line of output should contain an answer:
 "Found" — if the solution has been found.
 "No way" — if there is no Nth solution.
If the solution has been found, the second line of output should contain the
Nth solution in the same format as in input.
Example(s)
sample input

sample output

8 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Found 1 2 1 3 4 5 2 2 4 6 7 1 3 7 5 1 8 6 2 1 3 4 5 7 8 6 7 2 3 5 8

sample input

sample output

7 100000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

No way

This is the first example above: