题目描述

有 $k$ 个棋盘。每个棋盘大小为 $n\times m$ ，上面有 $3$ 个位置是 $0$，其他是 $1$。

现在a和b轮流操作，每次操作需要指定一个棋盘，在该棋盘上选定一行或者选定一列或者选定一行一列，将其全部变成0。但是要保证操作前后棋盘至少一个格子数字变了。

不能操作就输了。问是否先手必胜。

输入格式

输入的第一行包含一个正整数 $k$ 表示棋盘总数，保证 $1 \le k \le 10^5$。

接下来 $k$ 组数据，第 $i$ 组数据共4行，描述第 $i$ 张棋盘的样子：

• 第1行用空格隔开的两个正整数 $n,m$ 分别表示棋盘的行数和列数，保证 $1\le n,m \le 500$ 。
• 第2-4行，每行用空格隔开的两个正整数 $x,y$ 表示该棋盘上为0的位置，保证互不相同且 $1\leq x\leq n, 1\leq y\leq m$ 。

输出格式

如果先手必胜，输出一个字符串 OvO，否则输出一个字符串 QAQ。

1
2 3
1 1
2 1
2 2

OvO

一开始棋盘为：

011
001

先手只需要选中第1行第2列即可全部清零，从而后手无法操作，先手获胜。

1
4 4
1 1
1 2
4 2

QAQ

题目使用协议

来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）。

以下『本仓库』皆指 THUPC2024 官方仓库（https://gitlink.org.cn/thusaa/thupc2024final）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；
2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；
3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库的 github 地址。