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.