Description

Watching the world-famous scenery of Country $L$—Mount Cangwu—during late autumn is always a pleasant thing.

Mount Cangwu has $n$ peaks, numbered from $1$ to $n$. At the beginning, the summits of all $n$ peaks are covered by autumn fog, so their heights cannot be distinguished.

At the same time, peak $i$ is called an intermediate peak if and only if its height is exactly the average of the heights of peak $i-1$ and peak $i+1$ (in particular, peak $1$ and peak $n$ are not intermediate peaks). In the Mount Cangwu area, flags are traditionally hung at the foot of some intermediate peaks. Initially, there are no flags at the foot of any peak.

There are $m$ days, and each day one of the following events happens:

• Fog clears / fog returns: the autumn fog at the summit of peak $x$ clears, or gathers again.
• Flag raised / flag lowered: the flag at the foot of peak $x$ is hung up, or taken down.
• Visitor: a mountaineering enthusiast visits Mount Cangwu to climb peak $x$, and hopes to know its altitude on that day.

The enthusiasts learn heights in two ways: directly observing the altitude of peaks that are not covered by autumn fog, or using the “intermediate peak” information given by the flags at the feet of peaks on that day to deduce the heights of the remaining peaks as much as possible. Other methods are not allowed, including but not limited to communicating with previous visitors to share information.

Can you determine whether each enthusiast can know the height of the target peak?

Input Format

The first line contains two positive integers $n$ and $m$, representing the number of peaks in Mount Cangwu and the number of days the events last.

The next $m$ lines each contain two positive integers $op, x$, where $op \in \{1,2,3\}$. Specifically:

• For $op = 1$, it is guaranteed that $1 \le x \le n$. This means: if the summit of peak $x$ is foggy, it becomes fog-free; if it is fog-free, it becomes foggy.
• For $op = 2$, it is guaranteed that $2 \le x < n$. This means: if there is no flag at the foot of peak $x$, a flag is raised; if there is already a flag, it is lowered.
• For $op = 3$, it is guaranteed that $1 \le x \le n$. This means a mountaineering enthusiast who wants to climb peak $x$ visits.

Output Format

Output several lines. Each line contains one boolean value, in order, indicating whether each enthusiast can know the height: output $1$ if they can, and $0$ otherwise.

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

0
1

5 6
1 1
1 3
2 2
2 3
2 4
3 5

1

Hint

[Sample Explanation #1]

Without any intermediate-peak information, the first enthusiast cannot know the height of the peak covered by autumn fog.

When the second enthusiast visits, the heights of peak $1$ and peak $3$ are known, and peak $2$ is an intermediate peak, so the height of peak $2$ can be obtained by taking the average.

[Constraints]

This problem uses bundled testdata. You must pass all test points in a Subtask to get the score of that Subtask.

• Subtask #1 (7 points): $n \le 5$, $m \le 10$.
• Subtask #2 (13 points): $n, m \le 100$.
• Subtask #3 (15 points): $n, m \le 2000$.
• Subtask #4 (20 points): $n, m \le 10^5$.
• Subtask #5 (20 points): all events with $op = 1$ occur after all events with $op = 2$.
• Subtask #6 (25 points): no special constraints.

For all testdata, it is guaranteed that $3 \le n \le 5 \cdot 10^5$, $1 \le m \le 5 \cdot 10^5$.

Translated by ChatGPT 5