QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 512 MB

# 8748. 简单博弈

统计

题目描述

有 $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