题目描述

对于每一对数，你需要从中选一个数放入数组 $A$，另一个数放入数组 $B$。也就是说，对于每一对 $(x, y)$，可以进行以下两种选择之一：

• 将 $x$ 加入数组 $A$，将 $y$ 加入数组 $B$；
• 将 $y$ 加入数组 $A$，将 $x$ 加入数组 $B$。

当所有数对的选择都完成后，数组 $A$ 和数组 $B$ 的长度将相等。

对于一个数组 $C$，记 $\operatorname{mex}(C)$ 表示没有在数组 $C$ 中出现的最小非负整数。例如，若 $C = [0, 1, 4, 1, 2],$ 则 $\operatorname{mex}(C) = 3$，因为数字 $0$、$1$ 和 $2$ 在数组中出现了，而数字 $3$ 没有。若 $C = [1, 2, 3],$ 则 $\operatorname{mex}(C) = 0$，因为数字 $0$ 没有在数组中出现。

你需要最大化 $\operatorname{mex}(A) + \operatorname{mex}(B).$

在初始的数对集合之后，会给出 $q$ 个询问。每个询问要么向集合中添加一个数对，要么从集合中删除一个数对。在每次询问之后，你需要针对当前的数对集合，重新求出 $\operatorname{mex}(A) + \operatorname{mex}(B)$ 的最大可能值。

重要的是，在每次询问之后，你可以重新选择所有数对中数字的分配方式。也就是说，之前的选择不会限制后续的答案。

输入格式

第一行包含两个整数 $n$ 和 $q$ $(1 \le n \le 2 \cdot 10^5, 0 \le q \le 2 \cdot 10^5)$ —— 初始的数对个数以及询问的个数。

接下来的 $n$ 行给出初始的数对。 其中第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ $(0 \le a_i \le b_i \le 10^9)$。

再接下来的 $q$ 行给出询问。每个询问为以下两种格式之一： $\texttt{+ } x \ y$ 或 $\texttt{- } x \ y,$ 其中 $0 \le x \le y \le 10^9$。

查询 $\texttt{+ x y}$ 意味着将数对 $(x, y)$ 添加到集合中。

查询 $\texttt{- x y}$ 意味着从集合中删除一个数对 $(x, y)$。保证在执行这样的查询时，集合中至少存在一个这样的数对。

输出格式

输出 $q + 1$ 个整数。

第一个整数是对于初始的数对集合，$\operatorname{mex}(A) + \operatorname{mex}(B)$ 的最大值。

然后，在每次询问之后，输出对于当前数对集合，$\operatorname{mex}(A) + \operatorname{mex}(B)$ 的最大值。

每个答案输出在单独的一行中。

5 1
0 1
0 2
1 1
4 5
2 3
+ 4 5

8
9

5 0
1 1
1 1
1 1
1 1
0 0

4

5 0
1 2
2 3
3 4
4 5
5 6

0

5 0
2 2
3 3
0 1
3 4
0 10

6

5 0
1 3
4 5
0 9
0 0
5 6

3

提示

在第一个例子中，对于初始的数对集合，最优的选择例如是 $A = [0, 2, 1, 4, 3]$，$B = [1, 0, 1, 5, 2]$。此时 $\operatorname{mex}(A) = 5$，$\operatorname{mex}(B) = 3$，总和为 $8$。在添加数对 $(4, 5)$ 之后，可以选择例如 $A = [0, 2, 1, 5, 3, 4]$，$B = [1, 0, 1, 4, 2, 5]$，此时 $\operatorname{mex}(A) = 6$，$\operatorname{mex}(B) = 3$，总和为 $9$。

在第二个例子中，值的多重集为 $\{0, 0, 1, 1, 1, 1, 1, 1, 1, 1\}$。 最优的选择例如是 $A = [1, 1, 1, 1, 0]$，$B = [1, 1, 1, 1, 0]$。此时 $\operatorname{mex}(A) = \operatorname{mex}(B) = 2$，总和为 $4$。

在第三个例子中，没有一个值等于 $0$，因此无论如何选择，都无法使 $0 \in A$ 或 $0 \in B$。因此 $\operatorname{mex}(A) = \operatorname{mex}(B) = 0$，总和为 $0$。

在第四个例子中，最优的选择例如是 $A = [2, 3, 0, 3, 10]$，$B = [2, 3, 1, 4, 0]$。此时 $\operatorname{mex}(A) = 1$，$\operatorname{mex}(B) = 5$，总和为 $6$。

在第五个例子中，最优的选择例如是 $A = [3, 4, 9, 0, 6]$，$B = [1, 5, 0, 0, 5]$。此时 $\operatorname{mex}(A) = 1$，$\operatorname{mex}(B) = 2$，总和为 $3$。

计分

• （$2$ 分）：$n \le 20$，$q = 0$；
• （$7$ 分）：对于所有初始数对满足 $b_i = 10^9$，且对于所有询问满足 $y = 10^9$；
• （$8$ 分）：对于所有初始数对满足 $a_i = 0$，且对于所有询问满足 $x = 0$；
• （$9$ 分）：$n \le 500$，$q \le 500$；
• （$11$ 分）：$q = 0$；
• （$10$ 分）：所有询问均为 $\texttt{+ x y}$ 形式；
• （$9$ 分）：所有询问均为 $\texttt{- x y}$ 形式；
• （$13$ 分）：在任意时刻，对于当前集合中的任意三个数对，若第一个数对与第二个数对共享一个数字，且第二个数对与第三个数对共享一个数字，则存在一个数字同时属于这三个数对；
• （$20$ 分）：$n, q \le 10^5$；
• （$11$ 分）：无额外限制。

翻译由 DeepSeek V4 Pro 完成