First, consider the following problem:

\(4N\) cells are arranged in a circle. Strawberries are placed on \(2N\) of the \(4N\) cells. Find one way to choose \(2N\) consecutive cells such that exactly \(N\) of them contain a strawberry.

A solution always exists, so we can find one using prefix sums and brute force.

Proof of existence of a solution:

Label the cells clockwise from an arbitrary starting point as cells \(1, 2, \ldots, 4N\).

Let \(f(i)\) be the number of strawberries in cells \(i\) through \(i + 2N\). It suffices to show that there exists an \(i\) with \(f(i) = N\).

Since there are \(2N\) strawberries among the \(4N\) cells, \(f(1) + f(2N+1) = 2N\) holds. If \(f(1) = N\), the condition is satisfied. If \(f(1) < N\), since \(|f(i+1) - f(i)| \le 1\) and \(f(1) < N < f(2N+1)\), there must exist some value among \(f(2), f(3), \ldots, f(2N)\) that equals \(N\). The case \(f(1) > N\) is analogous.

Based on the above, we can find a solution satisfying the conditions by choosing one Hamiltonian cycle that traverses all cells of the \(2H \times 2W\) grid exactly once and performing the brute-force search above.

Such an Hamiltonian cycle can be constructed as follows:

By implementing the above appropriately, you can solve this problem.

Implementation example (Python3)

import sys

input = sys.stdin.readline

for _ in range(int(input())):
    h, w = map(int, input().split())
    s = [input() for _ in range(2 * h)]
    r = []
    c = []
    for j in range(0, 2 * w, 2):
        for i in range(1, 2 * h):
            r.append(i)
            c.append(j)
        for i in reversed(range(1, 2 * h)):
            r.append(i)
            c.append(j + 1)
    for j in reversed(range(2 * w)):
        r.append(0)
        c.append(j)
    a = [0] + [1 if s[r[i]][c[i]] == "o" else -1 for i in range(4 * h * w)]
    for k in range(4 * h * w):
        a[k + 1] += a[k]
    for k in range(2 * h * w):
        if a[2 * h * w + k] == a[k]:
            ans = [["A" for _ in range(2 * w)] for _ in range(2 * h)]
            for kk in range(2 * h * w):
                ans[r[k + kk]][c[k + kk]] = "B"
            for row in ans:
                print("".join(row))
            break

Proposed by: kyopro_friends