<|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.

409. Berland Flag
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard

The Berland is in trouble again. After the recent elections All-Berland Great Duma has divided into two coalitions: Blue-eyed coalition and Red-eyed coalition. On the independence day the following question was raised: what will the national flag look like? Both coalitions agreed that the flag should be a square of N2 x N2 cells, each of them painted blue of red. To make the flag acceptable for both coalitions, the following requirements must be held:
every row of the flag must contain exactly K blue cells
every column of the flag must contain exactly K blue cells
if we split the flag into squares of N x N cells (there will be N x N such squares), then every such square must contain exactly K blue cells. You are the chief programmers in Berland. So, making the flag model is your duty.
Input
First line of the input contains two integer numbers N and K (1 ≤ N ≤ 20, 0 ≤ K ≤ N2).
Output
Output description of the desired flag. Print N2 lines which consist of N2 characters '*' and '.', where '*' means blue cell and '.' means red cell. Output "NO SOLUTION" (without quotes), if there is no flag which satisfies both coalitions. If there are several solutions, output any of them.
Example(s)
sample input
sample output
2 2
*..*
.**.
.**.
*..*

sample input
sample output
3 1
*........
...*.....
......*..
.*.......
....*....
.......*.
..*......
.....*...
........*

<|response|>
## 1) Abridged problem statement (concise)

Given integers **N** and **K**, construct a grid of size **(N²) × (N²)** filled with:

- `*` (blue) or `.` (red)

such that:

1. Every **row** has exactly **K** blue cells.
2. Every **column** has exactly **K** blue cells.
3. If you partition the grid into **N × N blocks**, each block of size **N × N** must contain exactly **K** blue cells.

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

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

---

## 2) Key observations

1. The grid is naturally viewed as an **N × N array of blocks**, each block being **N × N**.
2. If we create one **base block** (top-left) with exactly **K** stars, and fill every other block by **permuting (cyclic shifting)** the base block, then:
   - each block still has exactly **K** stars (permutation preserves count),
   - and with the right shifts, global **row/column totals** become uniform.
3. A cyclic shifting scheme can make every global row/column "see" each base-row/base-column exactly once across blocks, which makes the total number of stars equal to the total stars in the base block, i.e. **K**.
4. This construction works for **all** `0 ≤ K ≤ N²`, so under given constraints a solution **always exists** (no need to output `"NO SOLUTION"`).

---

## 3) Full solution approach

Let `S = N²` be the side length of the full grid.

### Step A: Build the base `N × N` block with exactly `K` stars
Create the full `S × S` grid initialized with `.`.

In the top-left `N × N` block, put stars in row-major order:

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

Now the base block contains exactly `K` stars.

### Step B: Fill every other block using cyclic shifts
Index blocks by:
- block row `br` in `[0..N-1]`
- block col `bc` in `[0..N-1]`

and inside a block:
- inner row `i` in `[0..N-1]`
- inner col `j` in `[0..N-1]`

Define each 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]
\]

In implementation we can read `base` directly from `grid[0..N-1][0..N-1]`.

### Why it satisfies all constraints

- **Each block has K stars:** each block is just a rearrangement (cyclic shift) of the base block → star count preserved.
- **Each global row has K stars:** fix a global row `R = br*N + i`. As `bc` varies from `0..N-1`, `(i - bc) mod N` hits every base-row exactly once, so the total stars across that global row equals the total stars in the base block = `K`.
- **Each global column has K stars:** symmetric argument using `(j - br) mod N`.

### Complexity
Grid size is `S × S = N⁴` cells. With `N ≤ 20`, `S ≤ 400`, so max cells = 160,000.

- Time: `O(N⁴)`
- Memory: `O(N⁴)` (or print row-by-row if desired)

---

## 4) C++ implementation (detailed comments)

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

---

## 5) Python implementation (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])

    S = n * n  # full grid side length

    # Initialize grid with '.' (red)
    grid = [['.' for _ in range(S)] for _ in range(S)]

    # Step A: fill base block (top-left n x n) with exactly k stars in row-major order
    for c in range(k):
        r = c // n
        col = c % n
        grid[r][col] = '*'

    # Step B: fill each block (br, bc) as a cyclic shift of the base block
    for br in range(n):
        for bc in range(n):
            if br == 0 and bc == 0:
                continue  # base block already filled

            for i in range(n):
                for j in range(n):
                    R = br * n + i
                    C = bc * n + j

                    # (i - bc) mod n and (j - br) mod n
                    src_r = (i - bc) % n
                    src_c = (j - br) % n

                    # base block lives at rows 0..n-1, cols 0..n-1
                    grid[R][C] = grid[src_r][src_c]

    # Output
    sys.stdout.write("\n".join("".join(row) for row in grid))

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

This construction is deterministic, fast for `N ≤ 20`, and satisfies all three constraints simultaneously.
