<|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 with 31 cells. The cells are
numbered from 1 to 31 and laid out as the hexagon below; cells marked with "*"
are the special marked cells described later:

                 1     2
           3     4     5*    6     7
        8     9*   10    11    12*   13
          14    15    16*   17    18
       19    20*   21    22    23*   24
          25    26    27*   28    29
                30    31

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.

The three directions are: the horizontal rows, the "/" diagonals (lines going
from lower-left to upper-right), and the "\" diagonals (lines going from
upper-left to lower-right). Every one of the following 21 lines must contain
pairwise different numbers:

  Horizontal rows:
    1 2
    3 4 5 6 7
    8 9 10 11 12 13
    14 15 16 17 18
    19 20 21 22 23 24
    25 26 27 28 29
    30 31

  "/" diagonal rows:
    3 8
    1 4 9 14 19
    2 5 10 15 20 25
    6 11 16 21 26
    7 12 17 22 27 30
    13 18 23 28 31
    24 29

  "\" diagonal rows:
    7 13
    2 6 12 18 24
    1 5 11 17 23 29
    4 10 16 22 28
    3 9 15 21 27 31
    8 14 20 26 30
    19 25

Additionally, for each of the marked cells, the number in the marked cell and all numbers in adjacent cells must also differ from each other.

There are 7 marked cells: 5, 9, 12, 16, 20, 23 and 27. Each marked cell
together with its (up to six) neighbouring cells forms a group of 7 cells whose
numbers must all be distinct:

    marked 5  : { 1, 2, 4, 5, 6, 10, 11 }
    marked 9  : { 3, 4, 8, 9, 10, 14, 15 }
    marked 12 : { 6, 7, 11, 12, 13, 17, 18 }
    marked 16 : { 10, 11, 15, 16, 17, 21, 22 }
    marked 20 : { 14, 15, 19, 20, 21, 25, 26 }
    marked 23 : { 17, 18, 22, 23, 24, 28, 29 }
    marked 27 : { 21, 22, 26, 27, 28, 30, 31 }

(Each such group of 7 cells must use 7 different numbers, which is why K >= 7 is always required.)

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

1 ≤ N ≤ 10^18

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

<|response|>
## 1. Abridged problem statement

We have a fixed hexagonal Sudoku-like board with `31` cells. Each cell must contain a number from `1` to `K`.

A filling is valid if:

- In each of the 21 straight rows/diagonals, all numbers are different.
- In each of the 7 marked-cell neighbourhood groups, all numbers are different.
- Some cells may already be fixed in the input.

All valid solutions are ordered lexicographically by cells `1, 2, ..., 31`.

We must output the `N`-th valid solution, or print `No way` if fewer than `N` solutions exist.

Constraints:

```text
7 ≤ K ≤ 31
1 ≤ N ≤ 10^18
31 cells
```

---

## 2. Key observations needed to solve the problem

### Observation 1: This is graph coloring

Every constraint is an "all cells in this group must be different" constraint.

So we can model the board as a graph:

- Each cell is a vertex.
- Two cells are connected by an edge if they appear together in at least one all-different group.
- A valid Hexodoku filling is a proper coloring of this graph using colors `1..K`.

There are 28 all-different groups:

- 7 horizontal rows,
- 7 `/` diagonals,
- 7 `\` diagonals,
- 7 marked-cell neighbourhood groups.

For every group, all pairs of cells in that group become adjacent.

---

### Observation 2: Lexicographical order is natural DFS order

Solutions are compared by:

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

Therefore, if we perform DFS in this order:

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

and for every empty cell try values in increasing order:

```text
1, 2, ..., K
```

then complete solutions are generated in lexicographical order.

So we only need to count complete solutions until we reach the `N`-th one.

---

### Observation 3: Use candidate masks and forward checking

Naive DFS would repeatedly check all previous cells.

Instead, maintain for every cell:

```text
available values mask
```

When we assign value `v` to cell `i`, all later unfilled neighbours of `i` can no longer use `v`.

If some later cell loses its last available value, the current branch is impossible and can be pruned immediately.

---

### Observation 4: Need forbid counters for correct backtracking

The same value can be forbidden for a cell by several already-filled neighbours.

Example:

```text
cell j cannot use value 5 because two neighbours already use 5
```

When backtracking one neighbour, value `5` must still remain forbidden because the other neighbour still blocks it.

So we store:

```text
forbid_count[cell][value]
```

meaning:

> How many assigned neighbouring cells currently forbid this value for this cell?

A value is removed from the available mask only when the count changes from `0` to `1`.

A value is restored only when the count changes from `1` to `0`.

---

## 3. Full solution approach based on the observations

### Step 1: Build the graph

Create the 28 all-different groups.

For every group, connect every pair of cells inside it.

After this, `adj[i][j] = true` means cells `i` and `j` must contain different values.

---

### Step 2: Validate fixed cells

If two fixed adjacent cells have the same value, the puzzle is already impossible.

---

### Step 3: Initialize candidate masks

For every cell, initially all values `1..K` are available.

Then apply constraints from fixed cells:

If fixed cell `i` has value `v`, then every neighbour of `i` cannot use `v`.

---

### Step 4: Precompute future neighbours

DFS processes cells in increasing index order.

When assigning cell `i`, only later empty neighbours matter, because earlier cells are already assigned and later fixed cells were handled initially.

So for each cell `i`, store:

```text
fwd[i] = all empty cells j such that j > i and adj[i][j]
```

This makes each DFS step cheap.

---

### Step 5: DFS in lexicographical order

Function `search(i)` fills cells from `i` to `31`.

- If `i == 32`, one complete solution was found.
- If cell `i` is fixed, skip it.
- Otherwise, iterate over available values in increasing order.
- Assign value `v`.
- Remove `v` from all future neighbours.
- If no contradiction appears, recurse.
- Roll back all changes.

When the number of found solutions reaches `N`, stop and output the current board.

---

## 4. C++ implementation

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int k;
int64_t n;
array<int, 32> given;

int fwd[32][24], fwd_count[32];
int forbid_count[32][33];
unsigned avail[32];
int avail_count[32];
unsigned full_mask;
int64_t solutions;
int cur[32];
bool found;

void read() {
    cin >> k >> n;
    for(int i = 1; i <= 31; i++) {
        cin >> given[i];
    }
}

void search(int i) {
    if(i == 32) {
        if(++solutions == n) {
            found = true;
        }
        return;
    }
    if(given[i]) {
        search(i + 1);
        return;
    }

    unsigned cand = avail[i];
    const int* fw = fwd[i];
    int fn = fwd_count[i];
    while(cand && !found) {
        unsigned bit = cand & (~cand + 1);
        cand ^= bit;
        int v = __builtin_ctz(bit);

        bool dead = false;
        for(int t = 0; t < fn; t++) {
            int j = fw[t];
            if(forbid_count[j][v]++ == 0) {
                avail[j] &= ~bit;
                if(--avail_count[j] == 0) {
                    dead = true;
                }
            }
        }

        if(!dead) {
            cur[i] = v;
            search(i + 1);
        }

        for(int t = 0; t < fn; t++) {
            int j = fw[t];
            if(--forbid_count[j][v] == 0) {
                avail[j] |= bit;
                ++avail_count[j];
            }
        }
    }
}

void solve() {
    // All-different inside a group means every pair of its cells must differ,
    // so the board is a graph coloring instance: the numbers are colors and two
    // cells are adjacent when they share any of the 28 all-different groups -
    //
    // - the 7 rows running left to right (equal row_id),
    // - the 7 rows along the "/" direction (equal left_id),
    // - the 7 rows along the "\" direction (equal right_id),
    // - the 7 marked clusters, each a marked cell with its up to six
    //   neighbours, which is a clique of 7 and the reason 7 numbers are always
    //   needed.
    //
    // The N-th solution in lexicographic order comes from a depth-first search
    // that fills cells in index order 1..31 and at each cell tries the numbers
    // 1..K from small to large; this visits the complete colorings in exactly
    // lexicographic order, so we count leaves until the N-th. To keep each step
    // cheap we materialize every free cell's candidate set in avail[c] rather
    // than rebuilding it, backed by forbid_count[c][x] = how many filled
    // neighbours forbid number x on c (so x returns to avail[c] only once its
    // last blocker is undone). Placing a number at a cell removes it from every
    // later free neighbour's avail, and the branch is abandoned the instant one
    // of those neighbours is left with an empty avail (forward checking). The
    // per-node cost is proportional to a cell's not-yet-filled neighbours,
    // which shrinks with depth, so the search stays fast all the way down.
    //
    // Pre-filled cells are baked into the board before the walk starts (their
    // number is marked forbidden on every neighbour) and then skipped during
    // the walk; otherwise a given number on a late cell would only be
    // discovered at that depth, after the search had already wandered through
    // every free cell before it.

    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};
    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},
    };

    vector<vector<int>> members(28);
    for(int i = 1; i <= 31; i++) {
        members[row_id[i] - 1].push_back(i);
        members[7 + left_id[i] - 1].push_back(i);
        members[14 + right_id[i] - 1].push_back(i);
    }
    for(int c = 0; c < 7; c++) {
        for(int j = 0; j < 7; j++) {
            members[21 + c].push_back(clusters[c][j]);
        }
    }

    bool adj[32][32] = {};
    for(const auto& g: members) {
        for(int a: g) {
            for(int b: g) {
                adj[a][b] = (a != b);
            }
        }
    }

    for(int i = 1; i <= 31; i++) {
        fwd_count[i] = 0;
        for(int j = i + 1; j <= 31; j++) {
            if(adj[i][j] && !given[j]) {
                fwd[i][fwd_count[i]++] = j;
            }
        }
    }

    full_mask = ((1u << k) - 1) << 1;
    for(int i = 1; i <= 31; i++) {
        cur[i] = given[i];
        avail[i] = full_mask;
        avail_count[i] = k;
        for(int v = 0; v <= k; v++) {
            forbid_count[i][v] = 0;
        }
    }

    for(int i = 1; i <= 31; i++) {
        if(given[i]) {
            int v = given[i];
            for(int j = 1; j <= 31; j++) {
                if(adj[i][j] && forbid_count[j][v]++ == 0) {
                    avail[j] &= ~(1u << v);
                    avail_count[j]--;
                }
            }
        }
    }

    search(1);

    if(!found) {
        cout << "No way\n";
        return;
    }

    cout << "Found\n";
    for(int i = 1; i <= 31; i++) {
        cout << cur[i] << " \n"[i == 31];
    }
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}
```

---

## 5. Python implementation with detailed comments

```python
import sys

# ------------------------------------------------------------
# Read input
# ------------------------------------------------------------

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

# First two numbers are K and N.
K = data[0]
N = data[1]

# The next 31 numbers are the initial board.
# We use 1-based indexing, so cell_values[0] is unused.
given = [0] + data[2:33]

# ------------------------------------------------------------
# Board description
# ------------------------------------------------------------

# Horizontal row ids for cells 1..31.
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,
]

# "/" diagonal ids for cells 1..31.
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,
]

# "\" diagonal ids for cells 1..31.
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,
]

# The 7 marked-cell 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
# ------------------------------------------------------------

# There are 28 groups:
# 0..6   : horizontal rows
# 7..13  : "/" diagonals
# 14..20 : "\" diagonals
# 21..27 : marked clusters
groups = [[] for _ in range(28)]

# Add each cell to its three row/diagonal groups.
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)

# Add marked-cell clusters.
for c in range(7):
    groups[21 + c].extend(clusters[c])

# ------------------------------------------------------------
# Build adjacency graph
# ------------------------------------------------------------

# adj[a][b] is True if cells a and b must have different values.
adj = [[False] * 32 for _ in range(32)]

# Every pair of cells in the same group becomes adjacent.
for group in groups:
    for a in group:
        for b in group:
            if a != b:
                adj[a][b] = True

# ------------------------------------------------------------
# Optional validation of initially filled cells
# ------------------------------------------------------------

valid_initial = True

# If two adjacent given cells have the same value, there is no solution.
for i in range(1, 32):
    if given[i] == 0:
        continue
    for j in range(i + 1, 32):
        if given[j] != 0 and adj[i][j] and given[i] == given[j]:
            valid_initial = False

if not valid_initial:
    print("No way")
    sys.exit(0)

# ------------------------------------------------------------
# Precompute future neighbors
# ------------------------------------------------------------

# fwd[i] contains later empty cells adjacent to i.
# When assigning cell i, only these cells need candidate updates.
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)

# ------------------------------------------------------------
# Candidate masks and forbid counters
# ------------------------------------------------------------

# Bitmask with bits 1..K set.
# Bit 0 is unused.
full_mask = ((1 << K) - 1) << 1

# avail[i] stores the set of currently allowed values for cell i.
avail = [full_mask for _ in range(32)]

# avail_count[i] stores how many values are currently available.
avail_count = [K for _ in range(32)]

# forbid_count[i][v] tells how many assigned neighbors forbid value v for cell i.
forbid_count = [[0] * (K + 1) for _ in range(32)]

# Current board assignment.
cur = given[:]

# Apply constraints from pre-filled cells.
for i in range(1, 32):
    if given[i] != 0:
        v = given[i]
        bit = 1 << v

        # Every neighbor of this fixed cell cannot use value v.
        for j in range(1, 32):
            if adj[i][j]:
                if forbid_count[j][v] == 0:
                    avail[j] &= ~bit
                    avail_count[j] -= 1
                forbid_count[j][v] += 1

# If an empty cell already has no candidates, no solution exists.
for i in range(1, 32):
    if given[i] == 0 and avail_count[i] == 0:
        print("No way")
        sys.exit(0)

# ------------------------------------------------------------
# Lexicographical DFS
# ------------------------------------------------------------

solutions = 0
found = False


def search(i):
    """
    Tries to fill cells i..31.

    Because cells are processed in increasing order and values are tried in
    increasing order, complete assignments are generated lexicographically.
    """

    global solutions, found

    # If the desired solution was already found, stop recursion.
    if found:
        return

    # All cells have been assigned.
    if i == 32:
        solutions += 1

        # Check if this is the N-th solution.
        if solutions == N:
            found = True

        return

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

    # Candidate values for this cell.
    candidates = avail[i]

    # Try values in increasing order.
    while candidates and not found:
        # Extract lowest set bit.
        bit = candidates & -candidates

        # Remove that bit from candidate set.
        candidates ^= bit

        # Convert bit to value.
        v = bit.bit_length() - 1

        # Whether this assignment causes some future cell to have no candidates.
        dead = False

        # Apply assignment: future neighbors cannot use v.
        for j in fwd[i]:
            if forbid_count[j][v] == 0:
                avail[j] &= ~bit
                avail_count[j] -= 1

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

            forbid_count[j][v] += 1

        # Continue recursion only if forward checking did not fail.
        if not dead:
            cur[i] = v
            search(i + 1)

        # Roll back all changes made to future neighbors.
        for j in fwd[i]:
            forbid_count[j][v] -= 1

            if forbid_count[j][v] == 0:
                avail[j] |= bit
                avail_count[j] += 1


# Start search from cell 1.
search(1)

# ------------------------------------------------------------
# Output
# ------------------------------------------------------------

if not found:
    print("No way")
else:
    print("Found")
    print(*cur[1:])
```
