408之数据结构
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

众所周知，小苯是 qsmcgogo 的粉丝。
qsmcgogo 给小苯出了一道难题，他想要小苯在数组 a 上维护一个数据结构，支持添加和查询两种操作。
具体的：
1. 修改，给出两个数字 x, mask ，表示向 a 中加入一个满足：当前 a 中没有的，且大于等于 x 的 最小奇数或偶数（如果 mask 为 0 就是偶数，反之为奇数）。
2. 查询，给出一个数字 mask ，查询数组中的 mex0 或 mex1（如果 mask 为 0 则是 mex0，反之是 mex1）。

（其中，mex0 代表当前数组 a 中没有出现的最小非负偶数，mex1 代表当前数组 a 中没有出现的最小非负奇数。）

输入描述:

输入第一行包含两个正整数 n, q (1 \le n, q \le 2 \times 10^5)，分别代表数组 a 的初始长度，操作次数 q。
第二行包含 n 个正整数，代表初始时的 a (0 \le a_i \le 10^9) 数组。
接下来 q 行，每行先输入一个正整数 op 表示操作类型。
op = 1 代表修改操作，接下来会输入两个非负整数表示题目所述的 x, mask (0 \le x \le 10^9, mask \subseteq \{0, 1\})。
op = 2 代表查询操作，接下来会输入一个非负整数表示题目所述的 mask (mask \subseteq \{0, 1\})。

输出描述:

输出包含若干行，对于每个“查询”操作，输出对应查询的答案。
示例1

输入

复制 
5 5
0 1 3 5 7
1 6 1
2 0
2 1
1 1 0
2 0

输出

复制 
2
11
4

说明

本例中初始 a = [0, 1, 3, 5, 7]。
第一步，op = 1 表示修改操作，向 a 中加入大于等于 6 的最小未出现奇数，应该是 9。
第二步，op = 2 表示查询操作，查询 a 中未出现的最小偶数，答案是 2，因此输出 2。
第三步，op = 2 表示查询操作，查询 a 中未出现的最小奇数，答案是 11，因此输出 11。
第四步，op = 1 表示修改操作，向 a 中加入大于等于 1 的最小未出现偶数，应该是 2。
第五步，op = 2 表示查询操作，查询 a 中未出现的最小偶数，应该是 4，因此输出 4。