Problem Description

You have a multiset $S$, where each element is a segment. Initially, there are $n$ elements, and the $i$-th element is the segment $[l_i,r_i]$.

Then there are $q$ operations. In each operation, a segment $[L,R]$ is given. We simultaneously check every current element $[l_i,r_i]$. If it intersects with $[L,R]$, then the intersecting part is split out from the original segment, and the remaining parts are added back as new elements, while the original element is removed. The newly added elements do not participate in the current operation, and the segment $[L,R]$ itself is not added into $S$.

Formally, let $l'=\max(l_i,L)$ and $r'=\min(r_i,R)$. If $l'\le r'$, then:

• Add the segment $[l',r']$ to $S$.
• If $l_i<l'$, add the segment $[l_i,l'-1]$ to $S$.
• If $r'<r_i$, add the segment $[r'+1,r_i]$ to $S$.
• Remove the segment $[l_i,r_i]$ from $S$.

After each operation, output the current number of elements in $S$.

Note that if a newly generated element is identical to an existing one, all copies are kept. Similarly, when an element is removed, only one copy is deleted even if multiple identical copies exist.

Input Format

The first line contains two positive integers $n,q$, denoting the initial number of elements and the number of operations.

The next $n$ lines each contain two positive integers $l_i,r_i$, describing the initial segments $[l_i,r_i]$.

The next $q$ lines each contain two positive integers $L_i,R_i$, describing the segment $[L_i,R_i]$ given in each operation.

Output Format

Print $q$ lines, each containing a single integer — the number of elements after the corresponding operation.

5 3
1 1
10 10
3 3
3 3
1 10
2 8
3 10
1 3

7
8
9

10 10
2 9
10 10
2 8
2 5
2 9
2 2
1 10
10 10
2 9
2 2
2 10
1 6
1 10
3 4
2 9
1 9
3 7
2 10
2 10
2 10

11
16
16
28
29
29
34
34
34
34

Hint

Explanation for Sample 1

Initially there are $5$ segments: $[1,1],[10,10],[3,3],[3,3],[1,10]$.

For the first operation, the given segment is $[2,8]$. The segments intersecting it are $[3,3],[3,3],[1,10]$. After the operation, both $[3,3]$ remain unchanged, while $[1,10]$ becomes $[1,1],[2,8],[9,10]$. So there are $7$ elements in total.

For the second operation, the given segment is $[3,10]$. The intersecting elements are $[10,10],[3,3],[3,3],[2,8],[9,10]$. Among them, only $[2,8]$ changes, becoming $[2,2],[3,8]$. So there are $8$ elements in total.

For the third operation, the given segment is $[1,3]$. The only intersecting element that changes is $[3,8]$, which becomes $[3,3],[4,8]$. So there are $9$ elements in total.

Constraints

For all test cases, $1 \le n,q \le 5\times 10^5$, $1\le l_i \le r_i \le 10^9$, and $1 \le L_i \le R_i \le 10^9$.

• Special property: It is guaranteed that $L_i=1$.