Number Recovery

★★★★★

3.8

18 votes

Data Structures, Medium, Queue

Details

Submissions

Discussion

Editorial

Problem

A positive integer $X$ has been stolen. But luckily, $N$ hints are available, each described by two integers $a_i$ and $d_i$ , meaning that $|X-a_i| = d_i$ . The hints are numbered $1$ through $N$ . While some of those hints are helpful, some might be just a lie. Therefore, we are going to investigate the number $X$ under different possible scenarios.

Initially, we neither trust nor distrust any hint. That is, each hint may be either true or false. Then, in each of the $Q$ stages, we will either:

```
1 id
```
Entrust the -th hint (). That is, from now on, the -th hint must be true, unless declared otherwise in the future.
```
2 id
```
Distrust the -th hint (). That is, from now on, the -th hint must be false, unless declared otherwise in the future.
```
3 id
```
Neutralize the -th hint (). That is, from now on, the -th hint may be either true or false, unless declared otherwise in the future.

After each stage, you should determine the number of possible positive values $X$ and report such values in an increasing order. If there are infinitely many such values, print $-1$ instead.

Input

The first line contains two space-separated integers $N$ and $Q$ .

The $i$ -th of the following $N$ lines contains two space-separated integers $a_i$ and $d_i$ , describing the $i$ -th hint. It is guaranteed that no two hints are identical. That is, for every two different $i$ , $j$ , it is guaranteed that $a_i \ne a_j$ or $d_i \ne d_j$ .

Then, $Q$ lines follow, each containing two integers $t$ and $id$ — the type of an update and the index of an affected hint.

Output

After each stage, print the number of possible values of $X$ (in case there are infinitely many of them, print $-1$ ). If the number of possible values is finite and non-zero, in the same line, continue to print those values in an increasing order.

Constraints

$1 \leq N, Q \leq 200\,000$

$0 \leq a_i, d_i \leq 10^9$

$1 \leq t \leq 3$ for every stage (update).

$1 \leq id \leq N$ for every stage.

In tests worth 74 points in total, $a_i, d_i \leq 500\,000$ .

Note that the expected output feature for custom input is disabled for this contest.

Sample Input

Sample Output

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

In the sample test, we are given $N = 3$ hints and $Q = 10$ stages.
The first stage is described by a pair "1 1", which represents entrusting hint $1$ .
After this stage, $|X - 3| = 0$ must be true, so $X$ must be equal to $3$ . We report $1$ possible value: $3$ .

Then, the information that $|X-3| = 0$ is neutralized at stage $2$ . At this point, $X$ could be any positive integer, so we print $-1$ in the second line.

Contributers:

Pasapol Saowakon

Errichto Dębowski