## 1. Abridged problem statement

You are given a fixed hexagonal Sudoku-like board with 31 numbered cells. Each cell must contain a number from `1` to `K`.

Rules:

- In each of 21 straight lines of the board — 7 horizontal, 7 `/` diagonals, and 7 `\` diagonals — all numbers must be pairwise different.
- There are 7 special marked cells. For each marked cell, the marked cell and its adjacent cells form a group of 7 cells, and all numbers in that group must also be pairwise different.
- Some cells may already be filled.

Among all valid completions, ordered lexicographically by cells `1..31`, output the `N`-th solution. If fewer than `N` valid solutions exist, output `No way`.

Constraints:

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


---

## 2. Detailed editorial

### Model the puzzle as graph coloring

The board constraints are all "all numbers in this group must be different" constraints.

That means we can view the board as an undirected graph:

- Each cell is a vertex.
- Two vertices are connected by an edge if the corresponding cells appear together in at least one all-different group.
- Assigning a number to a cell is the same as coloring a vertex.
- A valid solution is a proper coloring of this graph using colors `1..K`.

There are 28 all-different groups:

1. 7 horizontal rows.
2. 7 `/` diagonal rows.
3. 7 `\` diagonal rows.
4. 7 marked-cell clusters.

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

---

### Lexicographical order

Solutions are ordered by the sequence:

```text
A1, A2, ..., A31
```

So to generate solutions in lexicographical order, we can do a depth-first search over cells in increasing index order:

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

At every empty cell, try values in increasing order:

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

This guarantees that completed assignments are visited in lexicographical order.

Therefore, we can count valid complete assignments as we find them. When the counter reaches `N`, the current assignment is the answer.

---

### Handling already-filled cells

The input may contain pre-filled cells.

The program first applies all constraints caused by these fixed cells before starting the DFS.

If cell `i` is fixed to value `v`, then every neighbor of `i` cannot use `v`.

This is recorded in candidate masks for every cell.

During DFS, fixed cells are skipped.

---

### Candidate masks

For every cell `i`, the solution maintains:

```cpp
avail[i]
```

as a bitmask of currently available values.

If bit `v` is set, then value `v` is still possible for cell `i`.

For example, if `K = 8`, the full mask is:

```text
bits 1..8 set
```

Bit `0` is unused.

The program also stores:

```cpp
avail_count[i]
```

the number of currently available values for cell `i`.

This makes it easy to detect dead branches: if some future cell has no available values, the current branch cannot lead to a solution.

---

### Why `forbid_count` is needed

A value can be forbidden for a cell by multiple already-filled neighbors.

For example, suppose cell `j` cannot use value `5` because two neighboring cells both use `5`. When we undo one of those neighbors during backtracking, value `5` should still remain forbidden because the other neighbor still blocks it.

So the program keeps:

```cpp
forbid_count[j][v]
```

meaning:

> How many already-assigned neighbors of cell `j` forbid value `v`?

A value is removed from `avail[j]` only when this count changes from `0` to `1`.

A value is restored to `avail[j]` only when this count changes from `1` to `0`.

---

### Forward checking

When the DFS assigns value `v` to cell `i`, only later unfilled neighbors of `i` need to be updated.

For every such neighbor `j`:

- Increase `forbid_count[j][v]`.
- If this was the first blocker, remove `v` from `avail[j]`.
- If `avail_count[j]` becomes zero, the branch is dead.

This is called forward checking.

It avoids exploring branches that are already impossible.

---

### Backtracking

After trying a value for a cell, the program must undo all changes before trying the next value.

For every affected future neighbor `j`, it decrements:

```cpp
forbid_count[j][v]
```

If the count becomes zero again, value `v` is restored into `avail[j]`.

---

### Complexity

The board has only 31 cells, so backtracking with strong constraints and forward checking is practical.

Each DFS step only updates future neighbors of the current cell, rather than recomputing all candidates from scratch.


---

## 3. C++ Solution

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


---

## 4. Python solution 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:])
```


---

## 5. Compressed editorial

Treat the board as a graph coloring problem. Each cell is a vertex, and two cells are adjacent if they belong to the same horizontal row, `/` diagonal, `\` diagonal, or marked-cell cluster. A valid Hexodoku solution is exactly a proper coloring with colors `1..K`.

To obtain the `N`-th lexicographical solution, perform DFS over cells `1..31`. For every empty cell, try values `1..K` in increasing order. This visits complete solutions in lexicographical order, so count them until the `N`-th one is reached.

For efficiency, maintain for every cell a bitmask `avail[i]` of currently possible values and `avail_count[i]`. Also maintain `forbid_count[i][v]`, the number of already assigned neighboring cells that forbid value `v` for cell `i`. When assigning value `v` to cell `i`, remove `v` from all later empty neighbors. If any such neighbor loses its last candidate, prune the branch. On backtracking, restore candidate masks using `forbid_count`.

Pre-filled cells are applied before DFS by forbidding their values in all neighboring cells, and then skipped during recursion. If DFS finishes before finding `N` solutions, print `No way`; otherwise print the found board.
