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

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

    int N, K;
    cin >> N >> K;

    int S = N * N; // Full grid side length

    // Initialize entire grid with '.' (red)
    vector<string> grid(S, string(S, '.'));

    // Step A: Fill the base block (top-left N x N) with exactly K stars.
    // Place stars in row-major order among the N*N cells of the base block.
    for (int c = 0; c < K; c++) {
        int r = c / N;     // row within base block
        int col = c % N;   // col within base block
        grid[r][col] = '*';
    }

    // Step B: For every block (br, bc), fill it as a cyclic shift of the base block.
    // base is grid[0..N-1][0..N-1].
    for (int br = 0; br < N; br++) {
        for (int bc = 0; bc < N; bc++) {

            // Skip the base block: it is already filled.
            if (br == 0 && bc == 0) continue;

            // Fill cells inside the block
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    // Destination coordinates in the full grid
                    int R = br * N + i;
                    int C = bc * N + j;

                    // Source coordinates in base block (cyclic shift)
                    // Use +N before %N to avoid negative indices in C++.
                    int src_r = (i + N - bc) % N; // (i - bc) mod N
                    int src_c = (j + N - br) % N; // (j - br) mod N

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

    // Under given constraints a solution always exists, so we print it.
    for (int r = 0; r < S; r++) {
        cout << grid[r] << "\n";
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

def solve() -> None:
    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.