## 1) Abridged problem statement

You are given multiple Tic-Tac-Toe (3×3) board positions. Player **Qc** uses **X** and moves first; player **He** uses **0** and moves second. Players alternate turns and play perfectly.
For each position, output one of:

- `X wins.`
- `0 wins.`
- `Game is a draw.`
- `Illegal position.` (if the position cannot occur in any valid game sequence)

Input ends with a line containing only `Qc`.

---

## 2) Detailed Editorial

### Key idea
Tic-Tac-Toe has a very small state space: each of 9 cells can be `{empty, X, 0}` → `3^9 = 19683` possible boards.
We can precompute, for every *reachable* board position, the game outcome under perfect play using **minimax DP**.

### State encoding (base-3)
Represent a board as an integer `state` in base 3 with 9 digits:

- digit 0 → empty (`.`)
- digit 1 → X
- digit 2 → 0

Cell index `i` (0..8) corresponds to row `i//3`, col `i%3`.

So:
- `get_cell(state, i)` extracts the i-th base-3 digit.
- `set_cell(state, i, v)` adds `v * 3^i` to set that digit (only used when currently 0).

### Win detection
There are 8 winning lines (3 rows, 3 cols, 2 diagonals).
`check_winner(state)` returns:
- `1` if X has 3-in-a-row
- `2` if 0 has 3-in-a-row
- `0` otherwise

### Whose turn?
Count placed marks: `cnt = number of non-empty cells`.

- If `cnt` is even → X to move (player = 1)
- If `cnt` is odd → 0 to move (player = 2)

This matches "X moves first" and strict alternation.

### DP meaning
Let `dp[state]` be the game result from this position with perfect play:

- `dp = 1`  → X will win
- `dp = -1` → 0 will win
- `dp = 0`  → draw

### Minimax recursion
From a state:
1. If someone already won → terminal:
   - winner X → `dp = 1`
   - winner 0 → `dp = -1`
2. Else if board full → `dp = 0`
3. Else:
   - determine current player (X or 0)
   - generate all moves to empty cells
   - if X to move: choose move maximizing `dp[next]`
   - if 0 to move: choose move minimizing `dp[next]`

### Detecting illegal positions (reachability)
Many of the 19683 base-3 boards are impossible in real play (wrong counts, moves after a win, etc.).
Instead of checking legality via rules, the code **marks states reachable from the empty board** by playing legal moves in order.

- Start with `reachable[0] = true`
- DFS from state 0:
  - stop expanding a state if it is already a win (game ends immediately)
  - otherwise try placing the correct next player's mark in any empty cell, and recurse
- Any input state not marked reachable is **illegal**.

This is robust and simple.

### Answering queries
For each board:
1. Encode into `state`.
2. If `reachable[state] == false` → `Illegal position.`
3. Else print based on `dp[state]`.

Complexity:
- Precompute explores only reachable states (≈ a few thousand).
- Each query is O(9) to encode + O(1) lookup.

---

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

const int STATES = 19683;
const int lines[8][3] = {{0, 1, 2}, {3, 4, 5}, {6, 7, 8}, {0, 3, 6},
                         {1, 4, 7}, {2, 5, 8}, {0, 4, 8}, {2, 4, 6}};

int dp[STATES];
bool reachable[STATES];

int get_cell(int state, int i) {
    for(int j = 0; j < i; j++) {
        state /= 3;
    }
    return state % 3;
}

int set_cell(int state, int i, int v) {
    int pw = 1;
    for(int j = 0; j < i; j++) {
        pw *= 3;
    }
    return state + v * pw;
}

int check_winner(int state) {
    for(auto& line: lines) {
        int a = get_cell(state, line[0]);
        int b = get_cell(state, line[1]);
        int c = get_cell(state, line[2]);
        if(a && a == b && b == c) {
            return a;
        }
    }
    return 0;
}

int count_pieces(int state) {
    int cnt = 0;
    for(int i = 0; i < 9; i++) {
        if(get_cell(state, i)) {
            cnt++;
        }
    }
    return cnt;
}

void precompute() {
    memset(reachable, false, sizeof(reachable));
    reachable[0] = true;

    function<void(int)> dfs = [&](int state) {
        int w = check_winner(state);
        if(w) {
            dp[state] = (w == 1) ? 1 : -1;
            return;
        }
        int cnt = count_pieces(state);
        if(cnt == 9) {
            dp[state] = 0;
            return;
        }
        int player = (cnt % 2 == 0) ? 1 : 2;
        bool maximizing = (player == 1);
        dp[state] = maximizing ? -2 : 2;
        for(int i = 0; i < 9; i++) {
            if(get_cell(state, i) == 0) {
                int nxt = set_cell(state, i, player);
                if(!reachable[nxt]) {
                    reachable[nxt] = true;
                    dfs(nxt);
                }
                if(maximizing) {
                    dp[state] = max(dp[state], dp[nxt]);
                } else {
                    dp[state] = min(dp[state], dp[nxt]);
                }
            }
        }
    };

    dfs(0);
}

string board[3];

void solve() {
    // We can do a DP over all 3^9 possible board states by doing a DFS from
    // the empty board. Each state encodes the board in base 3 (0 = empty, 1 =
    // X, 2 = O). For each state we compute the minimax outcome with perfect
    // play: 1 = X wins, -1 = O wins, 0 = draw. Only states reachable through
    // valid play are marked, so illegal positions are detected by checking
    // reachability. Each query then just encodes the board and looks up the
    // precomputed result. In practice only ~5k states out of 19683 are
    // reachable through valid play.

    int state = 0;
    for(int i = 0; i < 9; i++) {
        char c = board[i / 3][i % 3];
        if(c == 'X') {
            state = set_cell(state, i, 1);
        } else if(c == '0') {
            state = set_cell(state, i, 2);
        }
    }

    if(!reachable[state]) {
        cout << "Illegal position.\n";
    } else if(dp[state] == 1) {
        cout << "X wins.\n";
    } else if(dp[state] == -1) {
        cout << "0 wins.\n";
    } else {
        cout << "Game is a draw.\n";
    }
}

bool read() {
    cin >> board[0];
    if(board[0] == "Qc") {
        return false;
    }
    cin >> board[1] >> board[2];
    return true;
}

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

    precompute();

    while(read()) {
        solve();
    }

    return 0;
}
```

---

## 4) Python Solution

```python
import sys
sys.setrecursionlimit(1000000)

STATES = 3 ** 9  # 19683

# Winning triples in flattened 0..8 indexing
LINES = [
    (0, 1, 2), (3, 4, 5), (6, 7, 8),  # rows
    (0, 3, 6), (1, 4, 7), (2, 5, 8),  # cols
    (0, 4, 8), (2, 4, 6)              # diagonals
]

# dp[state] = 1  (X wins), 0 (draw), -1 (0 wins)
dp = [0] * STATES

# reachable[state] = whether this state can occur from empty board via legal play
reachable = [False] * STATES

# Precompute powers of 3 for fast digit operations
pow3 = [1] * 9
for i in range(1, 9):
    pow3[i] = pow3[i - 1] * 3

def get_cell(state: int, i: int) -> int:
    """Return base-3 digit at position i: 0 empty, 1 X, 2 0."""
    return (state // pow3[i]) % 3

def set_cell(state: int, i: int, v: int) -> int:
    """
    Return new state with digit i set to v by adding v * 3^i.
    Assumes digit i is currently 0.
    """
    return state + v * pow3[i]

def check_winner(state: int) -> int:
    """Return 1 if X wins, 2 if 0 wins, 0 otherwise."""
    for a, b, c in LINES:
        va = get_cell(state, a)
        if va != 0 and va == get_cell(state, b) and va == get_cell(state, c):
            return va
    return 0

def count_pieces(state: int) -> int:
    """Count number of non-empty cells."""
    cnt = 0
    for i in range(9):
        if get_cell(state, i) != 0:
            cnt += 1
    return cnt

def precompute():
    """DFS from empty board to mark reachable states and compute minimax dp."""
    reachable[0] = True

    def dfs(state: int):
        w = check_winner(state)
        if w != 0:
            # Terminal: someone already won
            dp[state] = 1 if w == 1 else -1
            return

        cnt = count_pieces(state)
        if cnt == 9:
            # Terminal: full board => draw
            dp[state] = 0
            return

        # Determine player to move by parity of pieces
        player = 1 if (cnt % 2 == 0) else 2  # 1=X, 2=0

        if player == 1:
            # X chooses the move with maximum dp outcome
            best = -2
            for i in range(9):
                if get_cell(state, i) == 0:
                    nxt = set_cell(state, i, 1)
                    if not reachable[nxt]:
                        reachable[nxt] = True
                        dfs(nxt)
                    best = max(best, dp[nxt])
            dp[state] = best
        else:
            # 0 chooses the move with minimum dp outcome
            best = 2
            for i in range(9):
                if get_cell(state, i) == 0:
                    nxt = set_cell(state, i, 2)
                    if not reachable[nxt]:
                        reachable[nxt] = True
                        dfs(nxt)
                    best = min(best, dp[nxt])
            dp[state] = best

    dfs(0)

def encode_board(rows) -> int:
    """Convert 3 strings of length 3 into base-3 encoded state."""
    state = 0
    for i in range(9):
        ch = rows[i // 3][i % 3]
        if ch == 'X':
            state = set_cell(state, i, 1)
        elif ch == '0':
            state = set_cell(state, i, 2)
    return state

def main():
    precompute()

    data = sys.stdin.read().splitlines()
    out = []
    i = 0
    while i < len(data):
        line = data[i].strip()
        i += 1

        if line == "Qc":
            break

        # Each test case: 3 lines of board, then an empty line (may be absent at EOF)
        row0 = line
        row1 = data[i].strip(); i += 1
        row2 = data[i].strip(); i += 1

        # Optional empty line separator
        if i < len(data) and data[i].strip() == "":
            i += 1

        state = encode_board([row0, row1, row2])

        if not reachable[state]:
            out.append("Illegal position.")
        else:
            if dp[state] == 1:
                out.append("X wins.")
            elif dp[state] == -1:
                out.append("0 wins.")
            else:
                out.append("Game is a draw.")

    sys.stdout.write("\n".join(out))

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

---

## 5) Compressed Editorial

Encode the board as a base-3 integer (`3^9` states). Precompute with DFS from the empty board only, alternately placing X then 0; stop expanding after a win. Mark visited states as `reachable` (legal positions). Compute minimax `dp[state]` where X maximizes and 0 minimizes among children; terminal values are `1/-1/0` for X win / 0 win / draw. For each query, encode the input board; if not `reachable` print `Illegal position.`, else print result from `dp`.
