时空限制

2S/512M

题目描述

给定一个操作序列和一个初始为空的集合 $S$。操作序列包含以下两种类型：

操作 $1$：向集合 $S$ 中添加一个数 $x$。

操作 $2$：从集合 $S$ 中删除所有值为 $x$ 的数（如果 $S$ 内没有 $x$ ，则什么都不做）。

现有 $Q$ 次查询。每次查询给出一个区间 $[l, r]$，要求计算依次执行操作序列中第 $l$ 到第 $r$ 个操作后，集合 $S$ 的 $\text{mex}$（最小未出现非负整数）值。

apiadu 觉得这个问题太简单了。故对于每次查询 $[l, r]$，他可以在该区间内选择两个位置 $i, j$（满足 $l\leq i < j\leq r$）并交换这 $i,j$ 两个位置的操作，你的目标是帮助 apiadu 选择 $i ,j$ 使最终集合 $\text{mex} {(S)}$ 值最大。你只需要输出最大的 $\text{mex} {(S)}$ 即可。（每次询问独立，即交换操作不影响后续的询问，同时 apiadu 也可以选择不交换。）

$\text{mex} {(S)}$ 表示 $S$ 中最小未出现的非负整数。例如 $\text{mex}{(\{1,2,3\})} = 0$，$\text{mex}{(\{0,1,2\})} = 3$，$\text{mex}{(\{0,1,3\})} = 2$。

格式

输入格式

本题有多组测试数据。

第一行含有一个正整数 $T$，表示数据组数。

对于每组数据，第一行含有 $2$ 个正整数 $n , Q$，表示操作序列的长度和询问次数。

接下来 $n$ 行，每行含有 $2$ 个整数 $op_i ,x_i$，$op_i = 1$ 表示添加操作（添加数 $x_i$）。$op_i = 2$ 表示删除操作（删除所有值为 $x_i$ 的数）。

接下来 $Q$ 行，每行输入两个整数 $l_i, r_i$，表示一次查询区间 $[l_i, r_i]$。

输出格式

对于每次查询，输出一行一个整数，表示 apiadu 通过选择交换两个位置操作后能得到的最大 $\text{mex} {(S)}$ 。

样例

样例输入 #1

2
3 2
1 0
2 0
1 1
1 3
2 3
2 1
1 1
1 0
1 2

样例输出 #1

2
0
2

样例解释 #1

对于第一组测试数据：

• 第一个询问 $[1,3]$，只需要将第 $1$ 个操作与第 $2$ 个操作交换，得到 $S = \{ 0 , 1\}$，$\text{mex} (\{0 ,1 \}) = 2$。

• 第二个询问 $[2,3]$，无论怎样交换都会得到 $S = \{1\}$，$\text{mex} (\{1 \}) = 0$。

数据规模

对于 $10\%$ 的测试数据，$1 \leq T , n, Q \leq 10$。

对于 $30\%$ 的测试数据，$1 \leq T , n, Q \leq 100$。

对于 $100\%$ 的测试数据，$1 \leq n , Q \leq 5 \times 10^5$， $1 \leq T \leq 100$， $\sum n \leq 5 \times 10^5$，$\sum Q \leq 5 \times 10^5$，$op_i \in \{1, 2\}$，$0 \leq a_i \leq n$，$1 \leq l \leq r \leq n$。