Hexodoku#6741
Sudoku is an amazing game. Many people have fun solving it. They say that a legendary programmer had spent just 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 non-standard hexagonal Sudoku board:
The cells are numbered from to .
According to the rules, numbers (from to ) 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.
Must be different
Some numbers may already be placed in the cells according to the rules. You are to find -th solution in lexicographical order, if it exists.
Let A_i be the number in the cell in solution , and B_i — the number in the cell in solution . Solution is lexicographically smaller than solution , if such exists that for each where i < j: A_i = B_i and A_j < B_j.
First line of input contains two integers and .
7 \le K \le 31
1 \le N \le 100000
Second line contains integer numbers: A_i (1 \le i \le 31) is the number standing in the cell .
1 \le A_i \le K, or , if there is no number in this cell.
First line of output should contain an answer:
"Found" — if the solution has been found.
"No way" — if there is no -th solution.
If the solution has been found, the second line of output should contain the -th solution in the same format as in input.
This is the first example above:
Example 1