Problem Description

There are $k$ chessboards. Each chessboard has size $n \times m$. On each chessboard, exactly $3$ positions are $0$, and all other positions are $1$.

Now A and B take turns to make moves. In each move, a player must choose one chessboard, and on that chessboard choose a row, or choose a column, or choose both one row and one column, and set all cells in the chosen row and/or column to $0$. However, it must be guaranteed that at least one cell changes between before and after the move.

If a player cannot make a move, they lose. Determine whether the first player has a winning strategy.

Input Format

The first line contains a positive integer $k$, the total number of chessboards. It is guaranteed that $1 \le k \le 10^5$.

Then follow $k$ test cases. The $i$-th test case has 4 lines describing the $i$-th chessboard:

• Line 1 contains two positive integers $n, m$ separated by spaces, denoting the numbers of rows and columns of the chessboard. It is guaranteed that $1 \le n, m \le 500$.
• Lines 2 to 4 each contain two positive integers $x, y$ separated by spaces, indicating a position whose value is $0$ on this chessboard. These positions are guaranteed to be pairwise distinct, and $1 \leq x \leq n$, $1 \leq y \leq m$.

Output Format

If the first player has a winning strategy, output the string OvO. Otherwise, output the string QAQ.

1
2 3
1 1
2 1
2 2

OvO

1
4 4
1 1
1 2
4 2

QAQ

Hint

Initially, the chessboard is:

011
001

The first player only needs to select row 1 and column 2 to clear everything to $0$, so the second player cannot make a move. Therefore, the first player wins.

Source and Acknowledgements

From the THUPC2024 (Tsinghua University Student Programming Contest and Collegiate Invitational) Finals. Thanks to THUSAA for providing the problem.

For the testdata, statement, reference solution, editorial, etc., please refer to the THUPC official repository https://thusaac.com/public.

Translated by ChatGPT 5