<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

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.

7 ≤ K ≤ 31



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

1 ≤ Ai ≤ 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 N-th solution.


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:

<|response|>
## 1. Abridged Problem Statement

We have a hexagonal Sudoku-like board with 31 cells numbered `1..31`.

Each cell must contain a number from `1..K`.

Rules:

1. In every straight row of the board, in all 3 directions, all numbers must be different.
2. For each marked cell, the marked cell and all adjacent cells must also contain pairwise different numbers.
3. Some cells may already be fixed.

Find the `N`-th valid completed board in lexicographical order by cell numbers.

If it exists, print:

```text
Found
```

and the completed board.

Otherwise print:

```text
No way
```

---

## 2. Key Observations

### Observation 1: This is a graph coloring problem

Treat each cell as a vertex.

If two cells must contain different numbers, connect them with an edge.

Then we need to color this graph with colors `1..K`.

A valid board is exactly a valid coloring of this graph.

---

### Observation 2: Lexicographical order is easy to generate

Lexicographical order compares:

```text
cell 1, then cell 2, then cell 3, ..., then cell 31
```

So if we run DFS like this:

```text
for cell i = 1..31:
    try values from 1 to K in increasing order
```

then completed boards are generated in lexicographical order.

Therefore, we can count solutions until we reach the `N`-th one.

---

### Observation 3: Use bitmasks for candidate values

Since:

```text
K <= 31
```

we can store available values for each cell inside a 32-bit integer.

Bit `v` means value `v` is available.

Example:

```cpp
avail[i] = bitmask of values currently possible for cell i
```

---

### Observation 4: Forward checking is important

When we assign value `v` to cell `i`, every unfilled neighbor of `i` can no longer use value `v`.

If some future cell loses its last available value, we can immediately stop exploring this branch.

This pruning is essential.

---

### Observation 5: Need forbidden counters

Suppose a cell cannot use value `v` because several already-filled neighbors use `v`.

When backtracking one of those neighbors, we cannot immediately restore `v`, because another neighbor may still forbid it.

So we store:

```cpp
forbid_count[cell][value]
```

meaning:

```text
how many assigned neighbors currently forbid this value for this cell
```

Only when this count becomes zero can the value be restored.

---

## 3. Full Solution Approach

### Step 1: Build all-different groups

There are 28 groups:

1. 7 rows in the first direction.
2. 7 rows in the second direction.
3. 7 rows in the third direction.
4. 7 marked clusters.

Inside each group, every pair of cells must contain different numbers.

We build an adjacency matrix:

```cpp
adj[a][b] = true
```

if cells `a` and `b` must be different.

---

### Step 2: Precompute forward neighbors

DFS fills cells in increasing order.

When assigning cell `i`, only cells `j > i` can still be unfilled.

So for each cell `i`, precompute:

```cpp
fwd[i] = all later empty neighbors of i
```

This avoids repeatedly scanning all cells during DFS.

---

### Step 3: Initialize candidates

Initially, every empty cell can use all values `1..K`.

Then for every fixed cell with value `v`, remove `v` from all its neighbors.

---

### Step 4: DFS in lexicographical order

For each cell:

- If it is fixed, skip it.
- Otherwise, try all currently available values in increasing order.

When trying value `v`:

1. Assign `v`.
2. Remove `v` from all later adjacent empty cells.
3. If any of them has no candidates, prune.
4. Recurse.
5. Undo all changes.

When we reach cell `32`, one full solution was found.

If this is the `N`-th solution, stop.

---

### Complexity

The board size is fixed: only 31 cells.

The worst-case search is exponential, but strong constraints and forward checking make it fast enough.

Memory usage is tiny.

---

## 4. C++ Implementation with Detailed Comments

```cpp
#include <bits/stdc++.h>
using namespace std;

int K;
long long N;

int given[32];        // given[i] = fixed value of cell i, or 0
int cur[32];          // current assignment

bool adj[32][32];     // adj[a][b] = true if cells a and b must differ

vector<int> fwd[32];  // later empty neighbors of each cell

int forbid_count[32][33];
// forbid_count[cell][value] = number of assigned neighbors forbidding value

unsigned avail[32];   // bitmask of available values for each cell
int avail_count[32];  // number of available values

long long solutions = 0;
bool found = false;

unsigned full_mask;

/*
    DFS over cells in order 1..31.

    Because we process cells by increasing index and try values increasingly,
    complete boards are generated in lexicographical order.
*/
void dfs(int cell) {
    if (found) return;

    // All cells processed: one complete valid solution.
    if (cell == 32) {
        solutions++;
        if (solutions == N) {
            found = true;
        }
        return;
    }

    // Fixed cells are already assigned.
    if (given[cell] != 0) {
        dfs(cell + 1);
        return;
    }

    // Candidate values for this cell.
    unsigned candidates = avail[cell];

    while (candidates && !found) {
        // Extract the lowest set bit.
        // This gives the smallest available value.
        unsigned bit = candidates & -candidates;
        candidates ^= bit;

        int value = __builtin_ctz(bit);

        bool dead = false;

        /*
            Assigning 'value' to 'cell' forbids this same value
            in all later empty adjacent cells.
        */
        for (int nxt : fwd[cell]) {
            if (forbid_count[nxt][value] == 0) {
                avail[nxt] &= ~bit;
                avail_count[nxt]--;

                if (avail_count[nxt] == 0) {
                    dead = true;
                }
            }

            forbid_count[nxt][value]++;
        }

        if (!dead) {
            cur[cell] = value;
            dfs(cell + 1);
        }

        /*
            Undo all restrictions caused by assigning 'value' to 'cell'.
        */
        for (int nxt : fwd[cell]) {
            forbid_count[nxt][value]--;

            if (forbid_count[nxt][value] == 0) {
                avail[nxt] |= bit;
                avail_count[nxt]++;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> K >> N;

    for (int i = 1; i <= 31; i++) {
        cin >> given[i];
        cur[i] = given[i];
    }

    /*
        These arrays describe membership of every cell in the 3 row directions.

        row_id[i]   = row number in first direction
        left_id[i]  = row number in second direction
        right_id[i] = row number in third direction
    */
    static const int row_id[32] = {
        0,
        1, 1,
        2, 2, 2, 2, 2,
        3, 3, 3, 3, 3, 3,
        4, 4, 4, 4, 4,
        5, 5, 5, 5, 5, 5,
        6, 6, 6, 6, 6,
        7, 7
    };

    static const int left_id[32] = {
        0,
        2, 3,
        1, 2, 3, 4, 5,
        1, 2, 3, 4, 5, 6,
        2, 3, 4, 5, 6,
        2, 3, 4, 5, 6, 7,
        3, 4, 5, 6, 7,
        5, 6
    };

    static const int right_id[32] = {
        0,
        3, 2,
        5, 4, 3, 2, 1,
        6, 5, 4, 3, 2, 1,
        6, 5, 4, 3, 2,
        7, 6, 5, 4, 3, 2,
        7, 6, 5, 4, 3,
        6, 5
    };

    /*
        The 7 marked clusters.

        Every listed cluster is a clique:
        all cells inside it must contain pairwise different values.
    */
    static const int clusters[7][7] = {
        {3, 4, 8, 9, 10, 14, 15},
        {1, 2, 4, 5, 6, 10, 11},
        {6, 7, 11, 12, 13, 17, 18},
        {10, 11, 15, 16, 17, 21, 22},
        {14, 15, 19, 20, 21, 25, 26},
        {21, 22, 26, 27, 28, 30, 31},
        {17, 18, 22, 23, 24, 28, 29}
    };

    /*
        Build all 28 all-different groups.
    */
    vector<vector<int>> groups(28);

    for (int i = 1; i <= 31; i++) {
        groups[row_id[i] - 1].push_back(i);
        groups[7 + left_id[i] - 1].push_back(i);
        groups[14 + right_id[i] - 1].push_back(i);
    }

    for (int c = 0; c < 7; c++) {
        for (int j = 0; j < 7; j++) {
            groups[21 + c].push_back(clusters[c][j]);
        }
    }

    /*
        Build graph edges.

        If two cells occur in the same all-different group,
        they must have different values.
    */
    memset(adj, false, sizeof(adj));

    for (const auto& group : groups) {
        for (int a : group) {
            for (int b : group) {
                if (a != b) {
                    adj[a][b] = true;
                }
            }
        }
    }

    /*
        Optional robustness check:
        if two fixed adjacent cells have equal values, no solution exists.
        The statement says fixed numbers are already valid, but this is safe.
    */
    for (int i = 1; i <= 31; i++) {
        for (int j = i + 1; j <= 31; j++) {
            if (given[i] && given[j] && given[i] == given[j] && adj[i][j]) {
                cout << "No way\n";
                return 0;
            }
        }
    }

    /*
        Precompute later empty neighbors.

        During DFS, when cell i is assigned, only cells with larger index
        can still be unassigned.
    */
    for (int i = 1; i <= 31; i++) {
        for (int j = i + 1; j <= 31; j++) {
            if (adj[i][j] && given[j] == 0) {
                fwd[i].push_back(j);
            }
        }
    }

    /*
        Create bitmask containing values 1..K.

        Example:
        K = 3
        bits 1, 2, 3 are set.
    */
    full_mask = ((1u << K) - 1) << 1;

    for (int i = 1; i <= 31; i++) {
        avail[i] = full_mask;
        avail_count[i] = K;

        for (int v = 0; v <= K; v++) {
            forbid_count[i][v] = 0;
        }
    }

    /*
        Apply restrictions from fixed cells.
    */
    for (int i = 1; i <= 31; i++) {
        if (given[i] == 0) continue;

        int value = given[i];
        unsigned bit = 1u << value;

        for (int j = 1; j <= 31; j++) {
            if (!adj[i][j]) continue;

            if (forbid_count[j][value] == 0) {
                avail[j] &= ~bit;
                avail_count[j]--;
            }

            forbid_count[j][value]++;
        }
    }

    /*
        If some empty cell already has no possible value, there is no solution.
    */
    for (int i = 1; i <= 31; i++) {
        if (given[i] == 0 && avail_count[i] == 0) {
            cout << "No way\n";
            return 0;
        }
    }

    dfs(1);

    if (!found) {
        cout << "No way\n";
    } else {
        cout << "Found\n";
        for (int i = 1; i <= 31; i++) {
            if (i > 1) cout << ' ';
            cout << cur[i];
        }
        cout << '\n';
    }

    return 0;
}
```

---

## 5. Python Implementation with Detailed Comments

```python
import sys


def main():
    data = list(map(int, sys.stdin.read().split()))

    k = data[0]
    target_n = data[1]

    # 1-based indexing.
    given = [0] + data[2:33]

    cur = given[:]

    # Row ids in the first direction.
    row_id = [
        0,
        1, 1,
        2, 2, 2, 2, 2,
        3, 3, 3, 3, 3, 3,
        4, 4, 4, 4, 4,
        5, 5, 5, 5, 5, 5,
        6, 6, 6, 6, 6,
        7, 7,
    ]

    # Row ids in the second direction.
    left_id = [
        0,
        2, 3,
        1, 2, 3, 4, 5,
        1, 2, 3, 4, 5, 6,
        2, 3, 4, 5, 6,
        2, 3, 4, 5, 6, 7,
        3, 4, 5, 6, 7,
        5, 6,
    ]

    # Row ids in the third direction.
    right_id = [
        0,
        3, 2,
        5, 4, 3, 2, 1,
        6, 5, 4, 3, 2, 1,
        6, 5, 4, 3, 2,
        7, 6, 5, 4, 3, 2,
        7, 6, 5, 4, 3,
        6, 5,
    ]

    # Marked clusters.
    clusters = [
        [3, 4, 8, 9, 10, 14, 15],
        [1, 2, 4, 5, 6, 10, 11],
        [6, 7, 11, 12, 13, 17, 18],
        [10, 11, 15, 16, 17, 21, 22],
        [14, 15, 19, 20, 21, 25, 26],
        [21, 22, 26, 27, 28, 30, 31],
        [17, 18, 22, 23, 24, 28, 29],
    ]

    # Build all-different groups.
    groups = [[] for _ in range(28)]

    for i in range(1, 32):
        groups[row_id[i] - 1].append(i)
        groups[7 + left_id[i] - 1].append(i)
        groups[14 + right_id[i] - 1].append(i)

    for c in range(7):
        for cell in clusters[c]:
            groups[21 + c].append(cell)

    # Build adjacency matrix.
    adj = [[False] * 32 for _ in range(32)]

    for group in groups:
        for a in group:
            for b in group:
                if a != b:
                    adj[a][b] = True

    # Optional fixed-cell conflict check.
    for i in range(1, 32):
        for j in range(i + 1, 32):
            if given[i] and given[j] and given[i] == given[j] and adj[i][j]:
                print("No way")
                return

    # Precompute later empty neighbors.
    fwd = [[] for _ in range(32)]

    for i in range(1, 32):
        for j in range(i + 1, 32):
            if adj[i][j] and given[j] == 0:
                fwd[i].append(j)

    # Bitmask with values 1..k set.
    full_mask = ((1 << k) - 1) << 1

    # avail[i] is the bitmask of values still possible for cell i.
    avail = [full_mask for _ in range(32)]

    # Number of possible values for each cell.
    avail_count = [k for _ in range(32)]

    # forbid_count[cell][value] counts active blockers.
    forbid_count = [[0] * (k + 1) for _ in range(32)]

    # Apply fixed cells' restrictions.
    for i in range(1, 32):
        if given[i] == 0:
            continue

        value = given[i]
        bit = 1 << value

        for j in range(1, 32):
            if not adj[i][j]:
                continue

            if forbid_count[j][value] == 0:
                avail[j] &= ~bit
                avail_count[j] -= 1

            forbid_count[j][value] += 1

    # If an empty cell has no candidate from the start, no solution exists.
    for i in range(1, 32):
        if given[i] == 0 and avail_count[i] == 0:
            print("No way")
            return

    solutions = 0
    answer = None

    sys.setrecursionlimit(10000)

    def dfs(cell):
        nonlocal solutions, answer

        if answer is not None:
            return

        # Complete board found.
        if cell == 32:
            solutions += 1

            if solutions == target_n:
                answer = cur[:]

            return

        # Fixed cells are skipped.
        if given[cell] != 0:
            dfs(cell + 1)
            return

        candidates = avail[cell]

        # Try values in increasing order.
        while candidates and answer is None:
            bit = candidates & -candidates
            candidates ^= bit

            value = bit.bit_length() - 1

            dead = False

            # Assigning value to this cell forbids it in later neighbors.
            for nxt in fwd[cell]:
                if forbid_count[nxt][value] == 0:
                    avail[nxt] &= ~bit
                    avail_count[nxt] -= 1

                    if avail_count[nxt] == 0:
                        dead = True

                forbid_count[nxt][value] += 1

            if not dead:
                cur[cell] = value
                dfs(cell + 1)
                cur[cell] = 0

            # Undo restrictions.
            for nxt in fwd[cell]:
                forbid_count[nxt][value] -= 1

                if forbid_count[nxt][value] == 0:
                    avail[nxt] |= bit
                    avail_count[nxt] += 1

    dfs(1)

    if answer is None:
        print("No way")
    else:
        print("Found")
        print(*answer[1:])


if __name__ == "__main__":
    main()
```