{"problem":{"name":"[THUPC 2024 决赛] 简单博弈","description":{"content":"有 $k$ 个棋盘。每个棋盘大小为 $n\\times m$ ，上面有 $3$ 个位置是 $0$，其他是 $1$。 现在 A 和 B 轮流操作，每次操作需要指定一个棋盘，在该棋盘上选定一行或者选定一列或者选定一行一列，将其全部变成 $0$。但是要保证操作前后棋盘至少一个格子数字变了。 不能操作就输了。问是否先手必胜。 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10549"},"statements":[{"statement_type":"Markdown","content":"有 $k$ 个棋盘。每个棋盘大小为 $n\\times m$ ，上面有 $3$ 个位置是 $0$，其他是 $1$。\n\n现在 A 和 B 轮流操作，每次操作需要指定一个棋盘，在该棋盘上选定一行或者选定一列或者选定一行一列，将其全部变成 $0$。但是要保证操作前后棋盘至少一个格子数字变了。\n\n不能操作就输了。问是否先手必胜。\n\n## Input\n\n输入的第一行包含一个正整数 $k$ 表示棋盘总数，保证 $1 \\le k \\le 10^5$。\n\n接下来 $k$ 组数据，第 $i$ 组数据共 4 行，描述第 $i$ 张棋盘的样子：\n\n* 第 1 行用空格隔开的两个正整数 $n,m$ 分别表示棋盘的行数和列数，保证 $1\\le n,m \\le 500$。\n* 第 2-4 行，每行用空格隔开的两个正整数 $x,y$ 表示该棋盘上为 $0$ 的位置，保证互不相同且 $1\\leq x\\leq n, 1\\leq y\\leq m$ 。\n\n## Output\n\n如果先手必胜，输出一个字符串 `OvO`，否则输出一个字符串 `QAQ`。\n\n[samples]\n\n## Note\n\n一开始棋盘为：\n\n```\n011\n001\n```\n\n先手只需要选中第 1 行第 2 列即可全部清零，从而后手无法操作，先手获胜。\n\n**来源与致谢**\n\n来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）决赛。感谢 THUSAA 的提供的题目。\n\n数据、题面、标程、题解等请参阅 THUPC 官方仓库 <https://thusaac.com/public>","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10549","tags":["2024","THUPC"],"sample_group":[["1\n2 3\n1 1\n2 1\n2 2\n","OvO"],["1\n4 4\n1 1\n1 2\n4 2\n","QAQ"]],"created_at":"2026-03-03 11:09:25"}}