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

293. Game with Q an C
time limit per test: 0.25 sec.
memory limit per test: 65536 KB
input: standard
output: standard



Qc and He play the following game.
Each turn He writes one of the two letters "Q" or "C" on the fence. The new letter is added to the end of the string formed by the previous letters. Players move alternately and on his turn Qc can either swap two already written letters, or do nothing (pass). On his first turn Qc obviously passes.
Qc's goal is to play in such way that in each his odd turn (1,3,5,7,...) letters on the fence form a palindrome (word that is reading the same in either direction). Occasionally Qc knows the sequence of letters that He is going to say and now Qc wants to know whether his goal is achievable.
Help Qc to find an appropriate sequence of turns or say that such sequence does not exist.

Input
The first line of the input file contains n (1 <= n <= 2005), n means that He will write 2n-1 letters on the fence. The second line contains the sequence of 2n - 1 letters that He is going to say. Each letter is only "Q" or "C".

Output
On the first line of the output print word "Qc" if the Qc's goal is achievable, otherwise print "He". If the first line is "Qc" then the following lines of the output should each contain two numbers separated by one space. Here "0 0" indicates the doing nothing and "q c" indicates the swapping of letters at positions q and c.
If there are more than one solutions print any one.

Sample test(s)

Input
Test #1
4
QCCQCQQ

Test #2
1
Q

Output
Test #1
Qc
0 0
0 0
1 2
3 4
3 4
0 0
1 4

Test #2
Qc
0 0
Author:	Anton Golubev, Petrazavodsk SU
Resource:	Anton Golubev (Hedgehog)'s Contest #2 from Annual Summer Russian Teams Meeting in Petrozavodsk State University
Date:	August 26, 2005

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

He writes a known string `s` (only letters `Q` and `C`) of length `2n-1`, one character per turn, appending to the end.

After each character He writes, Qc makes a move:
- either swap any two already-written positions, or
- do nothing (`0 0`).
On Qc’s very first move he must pass.

Qc wants that **after each of his odd-numbered moves** (1st, 3rd, 5th, …), the current string on the fence is a **palindrome**.

Given `n` and `s`, decide if Qc can achieve this, and if yes output any valid list of `2n-1` moves.

---

## 2) Key observations

1. **Checkpoints are odd lengths.**  
   Qc’s odd-numbered moves happen when the fence length is `1, 3, 5, ..., 2n-1`.

2. **Odd-length palindrome over 2 letters is always possible given the multiset.**  
   For length `L` odd, the multiset can form a palindrome iff exactly one letter has odd count.  
   With only `Q` and `C`, the total count is odd, so **exactly one** of them is odd automatically.  
   Hence, a palindrome arrangement always exists for every prefix of odd length—Qc’s difficulty is doing it with limited swaps.

3. **Between two checkpoints, only two new letters are appended and Qc gets exactly two moves.**  
   From length `2i-1` to `2i+1`, He appends two letters; Qc can do at most one swap after each append ⇒ **at most 2 swaps** total to restore a palindrome at the new checkpoint.

4. **Commit to a canonical target palindrome for each checkpoint.**  
   If we decide a specific palindrome arrangement `target(i)` for each odd prefix length `2i+1`, we can aim to transform the current fence into that `target(i)` at each checkpoint.

5. **In this construction, the new target differs from the current fence in ≤ 4 positions.**  
   With the canonical construction below, when two letters are appended, the required `target` changes “locally”, so the fence and the new `target` mismatch in at most 4 indices.  
   - If mismatches > 4 → impossible in 2 swaps.
   - If mismatches are 0 / 2 / 4 → fixable by 0 / 1 / 2 swaps.

6. **Binary alphabet makes mismatch repair easy.**  
   If two strings have the same multiset and mismatch positions are:
   - 2 positions: swapping those two fixes everything.
   - 4 positions: they can be resolved by two swaps (pair the mismatches).

---

## 3) Full solution approach

We simulate the game and maintain an invariant:

> After every **odd** Qc move (i.e., at fence lengths `1,3,5,...`), the current fence equals our chosen `target` palindrome for that length.

### Canonical `target` palindrome for length `L = 2i+1`

Let `q = #Q` and `c = #C` in the prefix `s[0..2i]`.

1. **Center is forced by parity:**
   - if `q` is odd → center is `Q`
   - else center is `C`

2. Remove that center letter from counts, leaving both remaining counts even:
   - `rem_q`, `rem_c`

3. Put as many `QC` alternating pairs as possible symmetrically from the ends inward:
   - take `alt = min(rem_q, rem_c)` (this is even)
   - fill positions `(0,1, ... alt-1)` mirrored with pattern `Q,C,Q,C,...` on the left, and same on the right.

4. The rest (if any) must be all the majority letter; fill the remaining symmetric slots with that letter.

This yields a deterministic palindrome for each checkpoint.

### How to produce Qc’s moves

- At the very beginning:
  - He writes `s[0]`, Qc must output `0 0`.

- For each stage `i = 1..n-1` (target length becomes `2i+1`):
  1. He appends two letters (we put them into our simulated `fence` array).
  2. Build `target` for this prefix length.
  3. Collect mismatch indices where `fence[j] != target[j]` for `j in [0..2i]`.
  4. If mismatches > 4 → output `"He"` (impossible).
  5. Otherwise schedule Qc’s two moves:
     - 0 mismatches: `(0,0)`, `(0,0)`
     - 2 mismatches: `(0,0)`, swap(these two)
     - 4 mismatches: swap(first pair), swap(second pair)
  6. Commit `fence = target` on the prefix to keep the invariant.

Complexity:
- Building/scanning each prefix costs `O(i)`, total `O(n^2)` which is fine for `n ≤ 2005`.
- Memory `O(n)`.

---

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

```cpp
#include <bits/stdc++.h>
using namespace std;

/*
  p293 - Game with Q and C

  Strategy:
  - Maintain that after each odd Qc turn, the current fence equals a canonical
    palindrome "target" built from the multiset of the current odd-length prefix.
  - Between two odd turns, He appends exactly 2 letters and Qc has exactly 2 turns,
    i.e., at most 2 swaps to transform (old target + 2 appended letters) into new target.
  - For this canonical target, the Hamming distance is never > 4 in successful cases.
*/

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

    int n;
    string s;
    cin >> n >> s;

    int m = 2 * n - 1;                 // total number of Qc turns == total letters
    string fence(m, ' '), target(m, ' ');
    vector<pair<int,int>> actions;     // one action per Qc turn

    int q_count = 0, c_count = 0;
    auto add_letter = [&](char ch) {
        if (ch == 'Q') q_count++;
        else c_count++;
    };

    // First letter is written, Qc must pass
    fence[0] = s[0];
    add_letter(s[0]);
    actions.push_back({0, 0});

    // For each next checkpoint i (length = 2*i+1), we add two letters and fix.
    for (int i = 1; i < n; i++) {
        // He appends two letters between checkpoints
        char ch1 = s[2*i - 1];  // before Qc's even turn
        char ch2 = s[2*i];      // before Qc's odd turn

        fence[2*i - 1] = ch1;
        fence[2*i]     = ch2;
        add_letter(ch1);
        add_letter(ch2);

        // ---- Build canonical target palindrome of length 2*i+1 ----
        // Center index is i (0-based) because length is 2*i+1.
        target[i] = (q_count & 1) ? 'Q' : 'C';

        // Remaining counts after fixing the center letter:
        int rem_q = q_count, rem_c = c_count;
        // Remove one of the odd-count letter to make both even.
        if (rem_q & 1) rem_q--;
        else rem_c--;

        // Use as many alternating QC pairs as possible on both ends.
        int alt = min(rem_q, rem_c); // even number

        // Fill leftmost region [0..alt-1] with Q,C,Q,C,... and mirror it.
        for (int j = 0; j < alt; j += 2) {
            target[j]               = 'Q';
            target[j + 1]           = 'C';
            target[2*i - j]         = 'Q';
            target[2*i - (j + 1)]   = 'C';
        }

        // Fill the remaining symmetric slots (if any) with the majority letter.
        char filler = (rem_q > rem_c) ? 'Q' : 'C';
        int diff = abs(rem_q - rem_c); // even
        for (int j = alt; diff > 0; j++, diff -= 2) {
            target[j]       = filler;
            target[2*i - j] = filler;
        }

        // ---- Compare fence vs target on the prefix [0..2*i] ----
        vector<int> mis;
        for (int pos = 0; pos <= 2*i; pos++) {
            if (fence[pos] != target[pos]) {
                mis.push_back(pos + 1); // output is 1-indexed
            }
        }

        // Need at most 2 swaps => at most 4 mismatched positions
        if ((int)mis.size() > 4) {
            cout << "He\n";
            return 0;
        }

        // Schedule exactly two actions (Qc even turn, then Qc odd turn):
        if (mis.empty()) {
            actions.push_back({0, 0});
            actions.push_back({0, 0});
        } else if (mis.size() == 2) {
            actions.push_back({0, 0});
            actions.push_back({mis[0], mis[1]});
        } else { // size == 4
            actions.push_back({mis[0], mis[1]});
            actions.push_back({mis[2], mis[3]});
        }

        // Commit: after these two moves we consider the fence equal to target.
        for (int pos = 0; pos <= 2*i; pos++) fence[pos] = target[pos];
    }

    // If we never failed, output the action list
    cout << "Qc\n";
    for (auto [a,b] : actions) {
        cout << a << ' ' << b << '\n';
    }
    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

def solve():
    data = sys.stdin.read().strip().split()
    n = int(data[0])
    s = data[1]
    m = 2 * n - 1

    fence = [' '] * m
    target = [' '] * m
    actions = []

    q_count = 0
    c_count = 0

    def add_letter(ch: str):
        nonlocal q_count, c_count
        if ch == 'Q':
            q_count += 1
        else:
            c_count += 1

    # Initial: He writes first letter, Qc must pass
    fence[0] = s[0]
    add_letter(s[0])
    actions.append((0, 0))

    # Each stage i builds palindrome of length 2*i+1 by handling two new letters.
    for i in range(1, n):
        ch1 = s[2*i - 1]
        ch2 = s[2*i]

        fence[2*i - 1] = ch1
        fence[2*i] = ch2
        add_letter(ch1)
        add_letter(ch2)

        # ---- Build canonical target palindrome for length 2*i+1 ----
        target[i] = 'Q' if (q_count & 1) else 'C'

        rem_q = q_count
        rem_c = c_count
        # Remove one center letter (the one that was odd)
        if rem_q & 1:
            rem_q -= 1
        else:
            rem_c -= 1

        alt = min(rem_q, rem_c)  # even

        # Alternating QC pairs from outside inward, symmetric fill
        j = 0
        while j < alt:
            target[j] = 'Q'
            target[j + 1] = 'C'
            target[2*i - j] = 'Q'
            target[2*i - (j + 1)] = 'C'
            j += 2

        # Fill remaining symmetric middle with the majority letter
        filler = 'Q' if rem_q > rem_c else 'C'
        diff = abs(rem_q - rem_c)  # even
        j = alt
        while diff > 0:
            target[j] = filler
            target[2*i - j] = filler
            j += 1
            diff -= 2

        # ---- Find mismatches between fence and target on prefix [0..2*i] ----
        mismatches = []
        for pos in range(0, 2*i + 1):
            if fence[pos] != target[pos]:
                mismatches.append(pos + 1)  # 1-indexed for output

        if len(mismatches) > 4:
            sys.stdout.write("He\n")
            return

        # Two turns available: even then odd
        if len(mismatches) == 0:
            actions.append((0, 0))
            actions.append((0, 0))
        elif len(mismatches) == 2:
            actions.append((0, 0))
            actions.append((mismatches[0], mismatches[1]))
        else:  # 4 mismatches
            actions.append((mismatches[0], mismatches[1]))
            actions.append((mismatches[2], mismatches[3]))

        # Commit: consider fence fixed to target for the next stage
        for pos in range(0, 2*i + 1):
            fence[pos] = target[pos]

    # Output
    out = ["Qc"]
    out.extend(f"{a} {b}" for a, b in actions)
    sys.stdout.write("\n".join(out) + "\n")

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

If you want, I can also add a small verifier (checker) that simulates the game and confirms the produced swaps indeed keep palindromes at required turns.