All Tracks Data Structures Queues Basics of Queues Problem

Number Recovery
Tag(s):

Data Structures, Medium, Queue, 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, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

September Easy '18

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications

?