Number Recovery
Tag(s):

## Data Structures, Queue

Problem
Editorial
Analytics

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 $id$-th hint ($1 \le id \le N$). That is, from now on, the $id$-th hint must be true, unless declared otherwise in the future.
• 2 id
Distrust the $id$-th hint ($1 \le id \le N$). That is, from now on, the $id$-th hint must be false, unless declared otherwise in the future.
• 3 id
Neutralize the $id$-th hint ($1 \le id \le N$). That is, from now on, the $id$-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
3 10
3 0
0 3
6 3
1 1
3 1
1 2
3 2
1 3
3 3
1 1
1 2
2 1
1 3

SAMPLE OUTPUT
1 3
-1
1 3
-1
2 3 9
-1
1 3
1 3
0
0

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.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

September Easy '18

OTHER PROBLEMS OF THIS CHALLENGE
• Math > Basic Math
• Algorithms > Dynamic Programming