题解

把每张棋盘看成一个独立的 impartial game，最后做 Nim 异或即可。棋盘操作等价于在一个二分图上删行、删列或同时删一行一列（至少要删掉一个 1）。定义当前局面的 Sprague–Grundy 值为 $g$，则整局游戏先手必胜当且仅当所有棋盘的 $g$ 的异或不为零。

无洞棋盘的基准 SG

如果棋盘上全是 $1$，设 $f[n][m]$ 为 $n\times m$ 棋盘的 SG。一次操作可以走到 $(n-1,m)$、$(n,m-1)$、$(n-1,m-1)$ 三个状态，因此有

$$f[n][m]=\operatorname{mex}\{f[n-1][m],f[n][m-1],f[n-1][m-1]\}. $$

预处理 $1\le n,m\le500$，可验证 $f$ 始终在 $\{0,1,2,3\}$ 之间。
一个重要观察：当行数、列数都至少为 $4$ 时，只有 $3$ 个零洞不足以让某行/列没有 $1$，合法操作集合与“无洞”完全一致，后续也始终一致，因此此时 SG 直接等于 $f[n][m]$。

行数不超过 3 的情况压缩

若 $\min(n,m)\le3$，将棋盘按需要转置，使行数 $r\le3$。只要存在一列完全由 1 构成，就能保证所有未被清除的行/列都可操作；而本题只有 3 个零洞，非全 1 的列最多 3 列，其余都是“普通列”。

用行掩码（$r\le3$，因此最多 3 位）表示哪些行还存在；每一列用一个 3 位掩码表示本列中哪些行目前是 1。列被清除后掩码变为 0；清除某一行相当于把所有列掩码对应位去掉。这样，列掩码的取值只有 $0\sim7$ 共 8 种。

状态表示：rowMask（行掩码）以及长度为 8 的数组 cnt[mask]，表示当前掩码为 mask 的列有多少。初态把 3 个零洞刻进去即可，非特殊列都是全 1 掩码。因为只有 3 个零洞，特殊列不超过 3 列，其余计入某一项的计数。

转移

• 选一行：该行在 rowMask 中为 1，且存在列掩码含该位，才合法。清除后把所有列掩码的该位抹掉并重计频次，行位也从 rowMask 删除。
• 选一列：任选 mask>0 且计数非零的列，将其计数减一。
• 同时选一行和一列：行位与上一条相同；先按行清除更新所有掩码，再把目标列（清除位后所得的新掩码）计数减一。

取上述可达状态的 mex 即为当前 SG。状态规模随列数单调减少，行数仅 3 位，搜索空间极小；用 unordered_map 记忆化即可。

整体算法

1. 预处理无洞 SG 表 $f$（$500\times500$）。
2. 逐棋盘读取并转置使行数较小：
   • 若 $n,m\ge4$，直接取 $f[n][m]$。
   • 否则构造初始掩码计数，记忆化 DFS 求 SG。
3. 所有棋盘的 SG 异或非零则输出 OvO，否则 QAQ。

复杂度：预处理 $\mathcal{O}(NM)$，记忆化部分受行数 $\le3$、零洞仅 3 个的限制，单棋盘状态数在千级以内，整体轻松跑过上限。内存占用常数级。

参考代码

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

static int baseSG[505][505];

struct Key {
    uint8_t rowMask;
    array<uint16_t, 8> cnt;
    bool operator==(const Key& other) const {
        return rowMask == other.rowMask && cnt == other.cnt;
    }
};

struct KeyHash {
    size_t operator()(const Key& k) const noexcept {
        size_t h = k.rowMask;
        for (uint16_t v : k.cnt) {
            h = (h * 1000003u) ^ v;
        }
        return h;
    }
};

unordered_map<Key, int, KeyHash> memoSmall;

int sgSmall(uint8_t rowMask, const array<uint16_t, 8>& cnt) {
    bool hasOne = false;
    for (int m = 1; m < 8; ++m) if (cnt[m]) { hasOne = true; break; }
    if (!hasOne) return 0;
    Key key{rowMask, cnt};
    auto it = memoSmall.find(key);
    if (it != memoSmall.end()) return it->second;
    unordered_set<int> nxt;
    // Row moves
    for (int r = 0; r < 3; ++r) if (rowMask & (1 << r)) {
        bool rowHasOne = false;
        for (int m = 1; m < 8; ++m) if (cnt[m] && (m & (1 << r))) { rowHasOne = true; break; }
        if (!rowHasOne) continue;
        array<uint16_t, 8> ncnt{};
        for (int m = 0; m < 8; ++m) ncnt[m & ~(1 << r)] += cnt[m];
        nxt.insert(sgSmall(rowMask ^ (1 << r), ncnt));
    }
    // Column moves
    for (int m = 1; m < 8; ++m) if (cnt[m]) {
        array<uint16_t, 8> ncnt = cnt;
        ncnt[m]--;
        nxt.insert(sgSmall(rowMask, ncnt));
    }
    // Row + column moves
    for (int r = 0; r < 3; ++r) if (rowMask & (1 << r)) {
        for (int m = 1; m < 8; ++m) if (cnt[m] && (m & (1 << r))) {
            array<uint16_t, 8> ncnt{};
            for (int mm = 0; mm < 8; ++mm) ncnt[mm & ~(1 << r)] += cnt[mm];
            ncnt[m & ~(1 << r)]--; // remove chosen column
            nxt.insert(sgSmall(rowMask ^ (1 << r), ncnt));
        }
    }
    int mex = 0;
    while (nxt.count(mex)) ++mex;
    memoSmall[key] = mex;
    return mex;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // Precompute base SG without holes.
    for (int i = 1; i <= 500; ++i)
        for (int j = 1; j <= 500; ++j) {
            bool seen[4] = {};
            seen[baseSG[i - 1][j]] = true;
            seen[baseSG[i][j - 1]] = true;
            seen[baseSG[i - 1][j - 1]] = true;
            int g = 0; while (g < 4 && seen[g]) ++g;
            baseSG[i][j] = g;
        }

    int k; if (!(cin >> k)) return 0;
    int xorsum = 0;
    while (k--) {
        int n, m; cin >> n >> m;
        vector<pair<int,int>> zeroes(3);
        for (auto &p : zeroes) { cin >> p.first >> p.second; --p.first; --p.second; }
        if (n > m) { for (auto &p : zeroes) swap(p.first, p.second); swap(n, m); }
        int sg = 0;
        if (n >= 4) {
            sg = baseSG[n][m];
        } else {
            uint8_t rowMask = (1u << n) - 1;
            array<uint16_t, 8> cnt{}; cnt.fill(0);
            vector<uint8_t> colMask(m, rowMask);
            for (auto [r, c] : zeroes) colMask[c] &= ~(1u << r);
            for (uint8_t mask : colMask) cnt[mask]++;
            sg = sgSmall(rowMask, cnt);
        }
        xorsum ^= sg;
    }
    cout << (xorsum ? \"OvO\" : \"QAQ\") << '\\n';
    return 0;
}