K. Detect Symmetry
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an $$$n \times n$$$ grid, initially all white. You will repeatedly color cells black or white. After each update, output whether the black cells are vertically symmetric. That is, you can draw a vertical line which reflects all the black cells onto each other. Formally, a grid is vertically symmetric if there exists some $$$k$$$ such that for every $$$1 \le r, c \le n$$$, the cell on row $$$r$$$ and column $$$c$$$ is black if and only if the cell on row $$$r$$$ and column $$$k - c$$$$$$^{\text{∗}}$$$ is black.

$$$^{\text{∗}}$$$cells with $$$k - c \lt 1$$$ and $$$k - c \gt n$$$ are considered white cells for the purposes of this check.

Input

Each test contains multiple test cases. The first line contains the number of test cases, $$$t$$$ $$$(1 \le t \le 10^4)$$$. The description of the test cases follows.

For each test case: the first line contains 2 integers, $$$n$$$ $$$(1 \le n \le 10000)$$$, the size of the grid, and $$$q$$$ $$$(1 \le q \le 10^6)$$$, the number of queries. The next $$$q$$$ lines will contain 2 integers, $$$r_i$$$ and $$$c_i$$$ $$$(1 \le r_i, c_i \le n)$$$, indicating the row and column of the cell whose color should be flipped. If the cell was white, then it will be turned black, and if it was black, it will be turned white.

It is guaranteed that the sum of $$$q$$$ over all test cases does not exceed $$$10^6$$$.

—

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$5$$$ points.

Test $$$1-2$$$ satisfies $$$n \le 100$$$.

Tests $$$3-6$$$ guarantee that all queries will turn cells from white to black. That is, there are no cells which are affected more than once by any queries in a test case.

Tests $$$7-20$$$ satisfy no additional constraints.

Output

After each query, output '"YES"' (without quotes) if the black cells are vertically symmetric, and '"NO"' (without quotes) otherwise.

You can output '"YES"' and '"NO"' in any case (for example, strings '"yES"', '"yes"' and '"Yes"' will be recognized as a positive response).

Example
Input
2
4 4
1 2
2 1
2 3
2 4
5 8
1 1
1 2
1 3
1 4
1 3
1 2
2 1
1 4
Output
YES
NO
YES
NO
YES
YES
YES
YES
NO
YES
NO
YES