U535994 J-D 小梦的数据结构

小梦非常喜欢数据结构，这天他给小追出了一道数据结构题。 小追有一个长度为 $n$ 的数组 $a$ ，小梦希望他在数组上维护一个数据结构，支持修改和查询两种操作。具体的： $\rm 1.$ 修改：输入 $i,\ x$，执行 $a_i = x$。 $2.$ 查询：输入 $x$，查询：$a$ **中没出现过的**最小的不小于 $x$ 的非负整数并输出（$mex_x$）。 现在小梦给出了 $q$ 次操作，他要小追对 $a$ 数组执行这些修改操作，并将所有查询操作的答案都求出。但小追并不擅长数据结构，于是希望你帮他完成这个难题，请你帮帮他吧。

**本题有多组测试数据。** 输入的第一行包含一个正整数 $T$，表示数据组数。 接下来包含 $T$ 组数据，每组数据的格式如下： 第一行两个正整数 $n, q$，分别表示数组 $a$ 的长度，和小梦的操作次数。 第二行 $n$ 个非负整数 $a_i$，表示数组 $a$。 接下来 $q$ 行，每行一个操作，首先输入一个 $op$。 ​ $\bullet$ 如果 $op=1$，则再输入两个空格隔开的整数 $i\ x$，表示修改操作的两个参数。 ​ $\bullet$ 如果 $op=2$，则再输入一个整数 $x$，表示查询操作的参数。

对于每组测试数据： 对于每个修改操作，在单独的一行输出一个整数表示答案。

**【样例 1 解释】** 数组 $a=\{2,3,4,7,8,9,11,20\}$。 查询不小于 $19$ 的最小未出现非负整数 $mex_{19}$，结果为 $19$。 $......$ 修改 $a_7=12$。 此时再查询不小于 $11$ 的最小未出现非负整数 $mex_{11}$，结果就是 $11$。 **【数据范围】** 令 $N$ 表示 $T$ 组数据中 $n$ 的总和，$Q$ 表示 $q$ 的总和。 对于 $\rm 20\%$ 的数据有：$T = 1, 1 \leq N,Q \leq 1000$。 对于 $40\%$ 的数据有：$1 \leq T \leq 5, 1 \leq N, Q, a_i,x \leq 10^5$。 另对于 $20\%$ 的数据有：$1 \leq T \leq 5, 1 \leq N, Q \leq 10^5, 0 \leq a_i,x \leq 10^9$，且只包含查询操作。 对于所有的测试数据有： $1 \leq T \leq 10, 1 \leq N, Q \leq 2 \times 10^5, 0 \leq a_i,x \leq 10^9$。