19103번 - Boring Game 다국어

Yong Chol is playing a game with his brother. The game board is a $N \times N$ grid. Each cell of the grid contains a coin. Each coin is either heads up or tails up. The players take turns to flip coins. In each turn, the player selects a cell $(x, y)$ ($1 \le x, y \le N$) with a coin heads up, and also two integers $w$ and $h$ ($1 \le w \le x$, $1 \le h \le y$). After that, the player looks at the rectangle of cells with its opposite corners containing cells $(x - w + 1, y - h + 1)$ and $(x, y)$, and flips all coins in this rectangle, changing heads to tails and vice versa.

The player who cannot make a move loses the game.

The game with his little brother is so boring for Yong Chol that he wants to finish it immediately. But before doing that, Yong Chol wants to know who will win if the two players play optimally from now on. The board may be rather large, so its current state is given as a list of rectangles such that their union represents the cells with a coin heads up, and all other cells contain a coin tails up. Yong Chol is to take the next move. Can you help him find out who will win?

The first line of input contains an integer $T$, the number of test cases ($1 \le T \le 200$).

Each test case starts with a line containing two integers: $N$, the size of the board, and $M$, the number of rectangles ($1 \le N \le 10^9$, $1 \le M \le 10^5$).

Each of the next $M$ lines contains four integers $x_1$, $y_1$, $x_2$, and $y_2$: the coordinates of the two opposite corners of the rectangle ($1 \le x_i, y_i \le N$, $x_1 \le x_2$, $y_1 \le y_2$).

The total sum of $M$ over all test cases will not exceed $6 \cdot 10^5$. For at least $90$ percent of the test cases, $M$ will be smaller than $600$.

For each test case, if Yong Chol wins the game, print "Yong Chol", otherwise print "Brother".