题目描述

你有一个可重集 $S$，每个元素是一个线段。初始你有 $n$ 个元素，第 $i$ 个元素为线段 $[l_i,r_i]$。

接下来有 $q$ 次操作，每次操作给出一个线段 $[L,R]$。同时检查当前的每个元素 $[l_i,r_i]$。若其与线段 $[L,R]$ 有交，则将相交的部分从原线段中分割出来，然后将剩下的几部分作为新的元素加入，并把原来的元素删掉。新的元素不会参与本次操作，线段 $[L,R]$ 不会被加入 $S$。

形式化地，令 $l'=\max(l_i,L)$，$r'=\min(r_i,R)$，若 $l'\le r'$：

• 将线段 $[l', r']$ 加入 $S$。

• 若 $l_i<l'$，将线段 $[l_i,l'-1]$ 加入 $S$。

• 若 $r'<r_i$，将线段 $[r'+1,r_i]$ 加入 $S$。

• 从 $S$ 中删除线段 $[l_i,r_i]$。

每次操作后，请你输出当前的元素个数。

注意，若每次检查后产生的元素若与原来的某个元素相同，则保留多个。若删除元素时存在多个和当前元素相同的元素，则只删除其中一个。

输入格式

第一行两个正整数 $n,q$，表示初始元素个数和操作次数。

接下来 $n$ 行，每行两个正整数 $l_i,r_i$，表示每个初始元素 $[l_i,r_i]$。

接下来 $q$ 行，每行两个正整数 $L_i,R_i$，表示每次操作给出的区间 $[L_i,R_i]$。

输出格式

输出 $q$ 行，每行一个整数表示每次操作后的元素个数。

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

提示

【样例解释 1】

初始有 $5$ 个线段 $[1,1],[10,10],[3,3],[3,3],[1,10]$。

第一个操作给定线段 $[2,8]$，与其有交的线段有 $[3,3],[3,3],[1,10]$，操作后 $[3,3]$ 保持不变，$[1,10]$ 变为 $[1,1],[2,8],[9,10]$，共有 $7$ 个元素。

第二个操作给定线段 $[3,10]$，与其有交有 $[10,10],[3,3],[3,3],[2,8],[9,10]$，其中只有 $[2,8]$ 会变为 $[2,2],[3,8]$，共有 $8$ 个元素。

第三个操作给定线段 $[1,3]$，与其相交的会变化的元素只有 $[3,8]$ 会变为 $[3,3],[4,8]$，共有 $9$ 个元素。

【数据范围】

本题使用子任务捆绑。

对于所有测试数据，$1 \le n,q \le 5\times10^5$，$1\le l_i \le r_i \le 10^9$，$1 \le L_i \le R_i \le 10^9$。

• 特殊性质：保证 $L_i = 1$。