## 1. Abridged problem statement

Given an `N × N` grid (`1 ≤ N ≤ 20`) containing a set `Q` of marked cells (`1`), decide whether `Q` can be divided into two disjoint subsets `A` and `B` such that one subset can be transformed into the other by:

- rotating by `0`, `90`, `180`, or `270` degrees,
- then shifting by some vector.

If possible, print `YES` and output one valid subset `A` as an `N × N` binary grid. Otherwise print `NO`.

---

## 2. Detailed editorial

We need split the marked cells `Q` into two parts `A` and `B` such that:

```text
B = f(A)
```

where `f` is one of the allowed transformations: a rotation by a multiple of `90°`, followed by a translation.

Since `A` and `B` form a partition of `Q`, they must have equal size. Therefore, if `|Q|` is odd, the answer is immediately `NO`.

### Representing transformations

Use grid coordinates `(r, c)`.

The four rotations around the origin can be represented as:

```text
0°:   (r, c)
90°:  (c, -r)
180°: (-r, -c)
270°: (-c, r)
```

After rotation, we add a translation vector `(dr, dc)`.

So every transformation has the form:

```text
f(cell) = rotate(cell) + shift
```

### Reducing the number of transformations

There are infinitely many possible shifts, but we only need to try finitely many.

Let `c0` be any marked cell, for example the first one in row-major order.

Assume `c0 ∈ A`. Then `f(c0)` must be some other marked cell in `Q`.

So, for each rotation, we can try all shifts that map `c0` to another marked cell.

What if in the true solution `c0 ∈ B` instead? Then using the inverse transformation swaps the roles of `A` and `B`, so we still find a valid solution.

Thus, we try at most:

```text
4 * |Q|
```

candidate transformations.

Since `N ≤ 20`, `|Q| ≤ 400`, this is easily small enough.

### Checking one fixed transformation

For a fixed transformation `f`, we need know whether there exists a subset `A` such that:

```text
Q = A ∪ f(A)
A ∩ f(A) = ∅
```

Build a directed graph on cells of `Q`:

- each cell `x` points to `f(x)` if `f(x)` is also in `Q`.

Because `f` is bijective on the infinite grid, every cell has:

- out-degree at most `1`,
- in-degree at most `1`.

Therefore, connected components are only:

- paths,
- cycles.

Along such a component, cells must alternate between `A` and `B`.

For a path:

```text
v1 -> v2 -> v3 -> ... -> vk
```

- `v1` has no predecessor, so it cannot be in `B`; it must be in `A`.
- `vk` has no successor, so it cannot be in `A`; it must be in `B`.

Thus the path length must be even.

For a cycle, alternating is possible iff the cycle length is even.

So for each component, we color cells alternately `0/1`. If a component has odd length, this transformation fails.

If all components have even length, all cells colored `0` form one valid subset `A`.

### Complexity

Let `M = |Q| ≤ 400`.

There are `O(M)` transformations to try, and each check takes `O(N²)` or `O(M)` time.

Total complexity:

```text
O(M * N²)
```

which is tiny for `N ≤ 20`.

---

## 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;
vector<string> g;

void read() {
    cin >> n;
    g.assign(n, "");
    cin >> g;
}

void solve() {
    // We need to split Q into A and B such that B is the image of A under a
    // rotation by a multiple of 90 degrees followed by a translation. Since
    // N <= 20, |Q| <= 400 and we can afford to brute force over the
    // transformation. There are only four rotations to try, and for each one
    // we can fix the lex-smallest cell c0 of Q to lie in A. Then f(c0) must
    // be some other cell of Q, which leaves only |Q| candidate shift vectors
    // per rotation - O(|Q|) transformations in total. If c0 actually belongs
    // to B in the true partition, the inverse rotation handles that case, so
    // anchoring c0 in A loses nothing.
    //
    // Fix a transformation f = R^k + v. The requirement Q = A U f(A) induces
    // a functional graph on Q: draw a directed edge c -> f(c) whenever both
    // c and f(c) are in Q. Each vertex has in- and out-degree at most one,
    // so the components are simple paths and simple cycles. Along every
    // component the labels A/B must alternate, because c in A forces f(c)
    // in B and vice versa. A path endpoint with no out-edge is forced into
    // B, an endpoint with no in-edge into A, so the path needs even length.
    // Cycles also need even length, but f has order dividing 4 and so the
    // cycles have length 2 or 4 - the parity is automatic. The only test
    // worth running per transformation is "are all path components even?".
    //
    // If some f passes the test, we recover A by taking the cells coloured
    // first along each component and print it. If nothing works, the answer
    // is "NO".

    vector<pair<int, int>> cells;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            if(g[i][j] == '1') {
                cells.push_back({i, j});
            }
        }
    }

    int total = cells.size();
    if(total == 0) {
        cout << "YES" << '\n';
        for(int i = 0; i < n; i++) {
            cout << string(n, '0') << '\n';
        }
        return;
    }

    if(total % 2 != 0) {
        cout << "NO" << '\n';
        return;
    }

    auto rotate_k = [](int r, int c, int k) {
        for(int i = 0; i < k; i++) {
            int nr = c, nc = -r;
            r = nr;
            c = nc;
        }
        return make_pair(r, c);
    };

    auto in_q = [&](int r, int c) {
        return 0 <= r && r < n && 0 <= c && c < n && g[r][c] == '1';
    };

    auto [c0r, c0c] = cells[0];

    auto try_transform = [&](int k, int dr, int dc) -> bool {
        auto f = [&](int r, int c) {
            auto [nr, nc] = rotate_k(r, c, k);
            return make_pair(nr + dr, nc + dc);
        };
        auto f_inv = [&](int r, int c) {
            auto [nr, nc] = rotate_k(r - dr, c - dc, (4 - k) % 4);
            return make_pair(nr, nc);
        };

        vector<vector<int>> color(n, vector<int>(n, -1));

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(g[i][j] != '1' || color[i][j] != -1) {
                    continue;
                }

                int sr = i, sc = j;
                while(true) {
                    auto [pr, pc] = f_inv(sr, sc);
                    if(!in_q(pr, pc) || (pr == i && pc == j)) {
                        break;
                    }
                    sr = pr;
                    sc = pc;
                }

                int col = 0, length = 0;
                int cr = sr, cc = sc;
                while(color[cr][cc] == -1) {
                    color[cr][cc] = col;
                    col ^= 1;
                    length++;
                    auto [nr, nc] = f(cr, cc);
                    if(!in_q(nr, nc)) {
                        break;
                    }
                    cr = nr;
                    cc = nc;
                }

                if(length % 2 != 0) {
                    return false;
                }
            }
        }

        cout << "YES" << '\n';
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                if(g[i][j] == '1' && color[i][j] == 0) {
                    cout << '1';
                } else {
                    cout << '0';
                }
            }
            cout << '\n';
        }
        return true;
    };

    for(int k = 0; k < 4; k++) {
        auto [rr, rc] = rotate_k(c0r, c0c, k);
        for(auto [tr, tc]: cells) {
            if(tr == c0r && tc == c0c) {
                continue;
            }
            int dr = tr - rr, dc = tc - rc;
            if(try_transform(k, dr, dc)) {
                return;
            }
        }
    }

    cout << "NO" << '\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();
        solve();
    }

    return 0;
}
```

---

## 4. Python solution with detailed comments

```python
import sys


def rotate_k(r, c, k):
    """
    Rotate point (r, c) by k * 90 degrees around the origin.

    k = 0: (r, c)
    k = 1: (c, -r)
    k = 2: (-r, -c)
    k = 3: (-c, r)
    """
    for _ in range(k):
        r, c = c, -r
    return r, c


def solve():
    data = sys.stdin.read().strip().split()

    # Read N.
    n = int(data[0])

    # Read grid.
    grid = data[1:1 + n]

    # Collect all cells belonging to Q.
    cells = []
    for r in range(n):
        for c in range(n):
            if grid[r][c] == '1':
                cells.append((r, c))

    total = len(cells)

    # Empty set is trivially splittable.
    if total == 0:
        print("YES")
        for _ in range(n):
            print("0" * n)
        return

    # Two congruent parts must have equal size.
    if total % 2 == 1:
        print("NO")
        return

    # Check whether a cell is inside Q.
    def in_q(r, c):
        return 0 <= r < n and 0 <= c < n and grid[r][c] == '1'

    # Use the first marked cell as anchor.
    c0r, c0c = cells[0]

    def try_transform(k, dr, dc):
        """
        Try transformation:
            f(x) = rotate_k(x, k) + (dr, dc)

        Return the resulting subset grid if valid, otherwise None.
        """

        def f(r, c):
            # Apply rotation.
            nr, nc = rotate_k(r, c, k)

            # Apply translation.
            return nr + dr, nc + dc

        def f_inv(r, c):
            # Undo translation.
            r -= dr
            c -= dc

            # Undo rotation.
            return rotate_k(r, c, (4 - k) % 4)

        # color[r][c]:
        # -1 means unvisited,
        #  0 means chosen subset A,
        #  1 means transformed subset B.
        color = [[-1] * n for _ in range(n)]

        # Process every marked cell.
        for i in range(n):
            for j in range(n):
                # Skip cells not in Q or already visited.
                if grid[i][j] != '1' or color[i][j] != -1:
                    continue

                # Find start of the component.
                sr, sc = i, j

                while True:
                    pr, pc = f_inv(sr, sc)

                    # If predecessor is outside Q, this is path start.
                    # If predecessor is the original cell, this is a cycle.
                    if not in_q(pr, pc) or (pr == i and pc == j):
                        break

                    sr, sc = pr, pc

                # Traverse forward and color alternately.
                cr, cc = sr, sc
                current_color = 0
                length = 0

                while color[cr][cc] == -1:
                    # Assign color.
                    color[cr][cc] = current_color

                    # Alternate between 0 and 1.
                    current_color ^= 1

                    # Count component size.
                    length += 1

                    # Move to next cell under f.
                    nr, nc = f(cr, cc)

                    # Stop if next cell is outside Q.
                    if not in_q(nr, nc):
                        break

                    cr, cc = nr, nc

                # Odd component cannot be alternately split.
                if length % 2 == 1:
                    return None

        # Build output subset: cells colored 0.
        answer = []
        for r in range(n):
            row = []
            for c in range(n):
                if grid[r][c] == '1' and color[r][c] == 0:
                    row.append('1')
                else:
                    row.append('0')
            answer.append(''.join(row))

        return answer

    # Try all four rotations.
    for k in range(4):
        # Anchor after rotation.
        rr, rc = rotate_k(c0r, c0c, k)

        # Try mapping anchor to every other marked cell.
        for tr, tc in cells:
            if tr == c0r and tc == c0c:
                continue

            # Translation needed.
            dr = tr - rr
            dc = tc - rc

            result = try_transform(k, dr, dc)

            # If valid, print answer.
            if result is not None:
                print("YES")
                print("\n".join(result))
                return

    # Nothing worked.
    print("NO")


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

---

## 5. Compressed editorial

Let `Q` be the set of marked cells. If `|Q|` is odd, answer is `NO`.

Try all transformations of the form:

```text
f(x) = rotation(x) + shift
```

There are four rotations. To limit shifts, pick one marked anchor cell `c0`. In a valid solution, either `c0` belongs to the first part, or the inverse transformation handles the case. Therefore, for each rotation, try shifts that map `c0` to every other marked cell.

For a fixed transformation `f`, create directed edges:

```text
x -> f(x)
```

whenever both cells are in `Q`.

Since `f` is bijective, every vertex has in-degree and out-degree at most one, so components are paths or cycles. A valid partition exists exactly when every component has even length, because cells must alternate between the two subsets.

If all components are even, color them alternately and output one color class. If no transformation works, output `NO`.

Complexity is small: at most `4|Q|` transformations, each checked in `O(N²)`, with `N ≤ 20`.