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 non-standard 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 N-th solution in lexicographical order, if it exists.

Let Ai be the number in the cell i in solution A, and Bi — 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: Ai = Bi and Aj < Bj.

Input
First line of input contains two integers K and N.



Second line contains 31 integer numbers: Ai (1 ≤ i ≤ 31) is the number standing in the cell i.



Output
First line of output should contain an answer:



If the solution has been found, the second line of output should contain the N-th 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:




Online Contester Team © 2002 - 2010. All rights reserved.