## 1) A concise, abridged problem statement

Given integers **N** and **K**, construct an **(N²) × (N²)** grid of characters:

- `*` = blue cell
- `.` = red cell

such that:

1. Every **row** contains exactly **K** `*`.
2. Every **column** contains exactly **K** `*`.
3. If you partition the big grid into **N × N blocks** of size **N × N** (so there are **N × N** blocks total), then **each block** contains exactly **K** `*`.

If impossible, print `"NO SOLUTION"`. Otherwise print any valid grid.

Constraints: `1 ≤ N ≤ 20`, `0 ≤ K ≤ N²`.

---

## 2) Detailed editorial (how the solution works)

### Key observation
The constraints are very structured: besides global row/column constraints, we also require every **N×N sub-block** to have exactly **K** stars.

A clean way to satisfy all three simultaneously is:

1. Build one **base N×N block** with exactly **K** stars.
2. Copy that block into every other block, but with a carefully chosen **cyclic shift** so that:
   - row totals across blocks become uniform,
   - column totals across blocks become uniform,
   - and each block still has exactly K stars (because it's just a permutation of the base block).

### Step 1: Construct the base block
Create an `N×N` block (top-left block) and place stars in the first `K` positions in row-major order:

For `c = 0..K-1`:
- row = `c / N`
- col = `c % N`
- set `base[row][col] = '*'`

This ensures the base block contains exactly `K` stars.

### Step 2: Fill all blocks using cyclic shifts
Let the full grid be indexed as:

- block row `br` in `[0..N-1]`
- block col `bc` in `[0..N-1]`
- inside-block coordinates `i, j` in `[0..N-1]`

We define block `(br, bc)` as a cyclic shift of the base block:

\[
grid[br\cdot N + i][bc\cdot N + j] = base[(i - bc) \bmod N][(j - br) \bmod N]
\]

(Equivalent to what the C++ code does using `(i + N - bc) % N`, etc.)

So:
- Moving **right by one block** (`bc+1`) shifts the base **up by 1** in the within-block row index.
- Moving **down by one block** (`br+1`) shifts the base **left by 1** in the within-block col index.

### Why does this satisfy the requirements?

#### (A) Each N×N block has exactly K stars
A cyclic shift is a permutation of cells within the block, so it preserves the number of `*`. Therefore every block has exactly `K` stars.

#### (B) Every global row has exactly K stars
Fix a global row `R`. Write `R = br*N + i` (block row `br`, inner row `i`).

Consider the N blocks across this row: block columns `bc=0..N-1`.
Inside each block, the row used from the base is `(i - bc) mod N`.
As `bc` runs from `0..N-1`, `(i - bc) mod N` cycles through **all** base rows exactly once.

Let `s_r` be number of stars in base row `r`.
Then the total stars in global row `R` equals:

\[
\sum_{bc=0}^{N-1} s_{(i-bc)\bmod N} = \sum_{r=0}^{N-1} s_r = K
\]

because the base block contains exactly K stars total.

#### (C) Every global column has exactly K stars
Similarly fix a global column `C = bc*N + j`.
Over block rows `br=0..N-1`, the base column index `(j - br) mod N` cycles through all base columns exactly once, so the sum of stars over that global column is also the total stars in the base block, i.e. **K**.

### Existence
This construction works for **every** `0 ≤ K ≤ N²`, so `"NO SOLUTION"` is never needed under given constraints.

### Complexity
- Grid size is `(N²)² = N⁴` cells.
- `N ≤ 20` ⇒ max 160,000 cells, trivial.
- Time: `O(N⁴)`, Memory: `O(N⁴)` for storing the grid.

---

## 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 n, k;

void read() { cin >> n >> k; }

void solve() {
    // Initially, it seems like the problem might be solvable by some pruned
    // binary search, but it's not quite clear whether it would be fast enough.
    // However, going for a brute force and looking at N = 3 is fairly useful.
    // Particularly, there is a fairly simple pattern for K = 1 (which also
    // a pears to be given in the sample tests) - we start with a coloring in
    // the top left corner, and then consider column and row wise cyclic shifts
    // of the N x N block.
    //
    //     *........
    //     ...*.....
    //     ......*..
    //     .*.......
    //     ....*....
    //     .......*.
    //     ..*......
    //     .....*...
    //     ........*
    //
    // If we are too look at the brute force, we can notice that there is also a
    // similar pattern for K = 2: we will simply fill the first two cells in the
    // first N x N square. Because we cyclic shift, every column and row will
    // also have exactly K matches. Trivially, every N x N square will also have
    // K matches. It might not be immediately clear, but this construction can
    // be used for any 0 <= K <= N^2. Particularly, when we fill the first row
    // of the N x N, or K >= N, we will have to start filling the second row.
    // The first row can be thought of as "filling":
    //
    //     1) In terms of columns, each column will get N x floor(K / N)
    //        contribution, floor(K / N) each from the N different large
    //        squares.
    //
    //     2) In terms of rows, we will also get N x floor(K / N) contributions
    //        of N each, coming from the floor(K / N) large squares.
    //
    // Then the rest K % N, can be reduced for the K < N case which is easy to
    // see works.

    vector<string> grid(n * n, string(n * n, '.'));

    for(int c = 0; c < k; c++) {
        grid[c / n][c % n] = '*';
    }

    for(int br = 0; br < n; br++) {
        for(int bc = 0; bc < n; bc++) {
            if(br == 0 && bc == 0) {
                continue;
            }
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    grid[br * n + i][bc * n + j] =
                        grid[(i + n - bc) % n][(j + n - br) % n];
                }
            }
        }
    }

    for(int i = 0; i < n * n; i++) {
        cout << grid[i] << '\n';
    }
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

## 4) Python solution (same idea) with detailed comments

```python
import sys

def solve() -> None:
    # Read N and K
    data = sys.stdin.read().strip().split()
    n = int(data[0])
    k = int(data[1])

    size = n * n  # The grid is (N^2) x (N^2)

    # Initialize the full grid with '.' (red cells).
    # We'll build it as a list of lists for easy assignment,
    # then convert rows to strings at the end.
    grid = [['.' for _ in range(size)] for _ in range(size)]

    # Step 1: fill the base (top-left) N x N block with exactly K stars.
    # Place stars in row-major order among the first N*N cells.
    for c in range(k):
        r = c // n     # row inside base block
        col = c % n    # col inside base block
        grid[r][col] = '*'

    # Step 2: fill every other block (br, bc) with a cyclic shift of the base block.
    for br in range(n):           # block row
        for bc in range(n):       # block column
            if br == 0 and bc == 0:
                continue          # base block already done

            # Fill the N x N cells of this block
            for i in range(n):    # inner row
                for j in range(n):# inner col
                    # Destination in big grid:
                    R = br * n + i
                    C = bc * n + j

                    # Source from base block with cyclic shift:
                    src_r = (i - bc) % n
                    src_c = (j - br) % n

                    grid[R][C] = grid[src_r][src_c]

    # Print the grid
    out_lines = [''.join(row) for row in grid]
    sys.stdout.write("\n".join(out_lines))

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

---

## 5) Compressed editorial

Make an `N²×N²` grid split into `N×N` blocks of size `N×N`. Put `K` stars in the top-left block in row-major order. For block `(br, bc)`, copy the base block but cyclically shift:
`cell(i,j) := base((i-bc) mod N, (j-br) mod N)`.
Each block keeps `K` stars. In any global row, the shifts across `bc=0..N-1` visit every base row once, so the row total becomes total(base)=K; similarly for columns across `br`. Works for all `0 ≤ K ≤ N²`, so a solution always exists.
