Background

Problem setter: LinkyChristian.

Problem tester: Legitimity.

Story writer: Xiao Nuomi (小糯米).

Problem Description

Whether a hero or a fairy, when carrying out missions, it is hard to avoid some special “occupational diseases”. Among them, the one ranked first on the “Common Hero Occupational Disease List” is called “Acute Mana Poisoning”. Although mana poisoning on the surface looks like a high fever, if it is not completely removed each time, it will become a chronic illness, and the body will soon exceed its load limit. The treatment for mana poisoning is quite straightforward: find where mana is congested, press hard, and use a principle similar to traditional Chinese massage to rub the congested spot open. The specific treatment idea is as follows:

The mana meridians in the human body can be seen as an $n \times n$ grid. Similar to the classification of acupoints in traditional Chinese medicine, the “acupoints” where mana acts can also be roughly divided into yin and yang. For a more intuitive description, we represent yang mana acupoints as black dots on the grid. Mana congestion, in most cases, happens because using mana makes muscles tense, which causes originally yin acupoints to become yang, or yang to become yin. The so-called massage is to restore them to their proper states, thereby unblocking the mana. The sign that the massage is completed is whether, in this grid, there exists a polygon whose vertices are black dots and whose all edges are parallel to the grid.

Now, after a fierce battle, Chtholly has shown symptoms of acute mana poisoning again due to overusing mana. While examining her, Willem finds that there are $m$ mana acupoints showing yang reactions on her mana meridians. He will now perform $k$ massages. Each massage gives a point: if that point is currently yang (black), it becomes yin (white); otherwise it becomes yang (black).

Willem wants to know, after each massage, whether his treatment has already been completed.

Formal statement: Given an $n \times n$ grid with $m$ black points.

There are $k$ operations. Each operation toggles (black/white flip) one point. After each operation, determine whether there exists a polygon whose vertices are black points and whose all edges are parallel to the grid.

Input Format

The first line contains two numbers: $n, m$.
The next $m$ lines each contain two numbers $x, y$, indicating that point $(x, y)$ is a black point.
The next line contains one number $k$. Then the following $k$ lines each contain two numbers $x, y$, indicating one operation (i.e., a massage) on point $(x, y)$.

Output Format

Output $k$ lines. Each line contains Yes or No, indicating whether after this operation the treatment is completed, i.e., whether after each operation there exists a polygon whose vertices are black points and whose all edges are parallel to the grid.

100 3
1 1
2 2
1 2
5
5 5
2 1
2 1
5 1
2 5

No
Yes
No
No
Yes

Hint

For Sample 1, the initial state is:

After that, the states after each operation are, in order:

Constraints:
For $5\%$ of the testdata, $n \le 10, m \le 5, k \le 100$.
For $10\%$ of the testdata, $n, k \le 100$.
For $20\%$ of the testdata, $n, k \le 1000$.
For $80\%$ of the testdata, $n, k \le 5 \times 10^4$.
For another $10\%$ of the testdata, $k = 1$.
For $100\%$ of the testdata, $m \le n \le 10^5, k \le 10^5$.

Translated by ChatGPT 5