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.
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.