题目描述
有 k 个棋盘。每个棋盘大小为 n×m ,上面有3个位置是0,其他是1。
现在a和b轮流操作,每次操作需要指定一个棋盘,在该棋盘上选定一行或者选定一列或者选定一行一列,将其全部变成0。但是要保证操作前后棋盘至少一个格子数字变了。
不能操作就输了。问是否先手必胜。
输入格式
从标准输入读入数据。
输入的第一行包含一个正整数 k 表示棋盘总数,保证 1≤k≤105。
接下来 k 组数据,第 i 组数据共4行,描述第 i 张棋盘的样子:
- 第1行用空格隔开的两个正整数 n,m 分别表示棋盘的行数和列数,保证 1≤n,m≤500 。
- 第2-4行,每行用空格隔开的两个正整数 x,y 表示该棋盘上为0的位置,保证互不相同且 1≤x≤n,1≤y≤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