Time Limit: 10000/5000 MS (Java/Others)

Memory Limit: 153428/153428 K (Java/Others)

YongChol is playing a game with his brother. The board is a N*N grid filled with coins. The players take turns to flip coins.

In each turn, the player selects a cell (x, y) (1 <= x, y <= N) with a coin facing up and two integers w, h (1 <= w <= x, 1 <= h <= y), and flips all coins inside the rectangle which bottom-right cell is (x, y) and top-left cell is (x – w + 1, y – h + 1).

The player who cannot move any more loses.

The game with his little brother is so boring that he wants to finish the game immediately. YongChol wants to know who will win the game if the two players play optimally from now on.

In consideration of the large size of the board, initial board state is given with a list of rectangles, the union of which represents the cells with a coin facing up.

YongChol is to take the next move. Can you help him?

In each turn, the player selects a cell (x, y) (1 <= x, y <= N) with a coin facing up and two integers w, h (1 <= w <= x, 1 <= h <= y), and flips all coins inside the rectangle which bottom-right cell is (x, y) and top-left cell is (x – w + 1, y – h + 1).

The player who cannot move any more loses.

The game with his little brother is so boring that he wants to finish the game immediately. YongChol wants to know who will win the game if the two players play optimally from now on.

In consideration of the large size of the board, initial board state is given with a list of rectangles, the union of which represents the cells with a coin facing up.

YongChol is to take the next move. Can you help him?

The first line of input contains an integer T(1<=T<=200), the number of test cases.

Each test case begins with two integer N (1<=N<=1e9), M(1<=M<=100000), the size of the board and the number of rectangles respectively.

The next M lines each contains 4 integers, x1,y1,x2, y2(1<=xi,yi<=N), the coordinates of the top-left and bottom-right corner of the rectangle.

The total sum of M over all test cases will not exceed 600000.

For 90% of the test cases, M will be smaller than 600.

Each test case begins with two integer N (1<=N<=1e9), M(1<=M<=100000), the size of the board and the number of rectangles respectively.

The next M lines each contains 4 integers, x1,y1,x2, y2(1<=xi,yi<=N), the coordinates of the top-left and bottom-right corner of the rectangle.

The total sum of M over all test cases will not exceed 600000.

For 90% of the test cases, M will be smaller than 600.

提交代码