cats 的集合 1

Problem Description

此题输入/输出量较大，建议使用较快的读入方式，时间限制以关闭流同步的 cin/cout 为标准 cats 需要维护一个可重集 $S$。开始时，可重集中存在 $n$ 个元素 $p_1,p_2,\cdots,p_n$。然后，cats 对集合进行了 $m$ 次操作。操作分为以下 $5$ 种： 1 a：在可重集中加入元素 $a$。 2 a：将可重集中的每个元素都变为其与 $a$ 按位或运算的结果。 3 a：将可重集中的每个元素都变为其与 $a$ 按位与运算的结果。 4 a：将可重集中的每个元素都变为其与 $a$ 按位异或运算的结果。 5 a：查询可重集中每一个元素与 $a$ 按位异或运算结果中的最大值。

Input

第一行一个整数 $T$（$1\leq T\leq 1000$），表示测试数据的组数。 接下来包含 $T$ 组测试数据。 每组数据第一行为两个整数 $n,m$ $(1\leq n,m\leq 2\times 10^5)$，分别表示开始时 $S$ 中元素的个数，cats 需要进行的操作次数。 接下来一行包含 $n$ 个整数 $p_1,p_2,\cdots,p_n$ $(0\leq p_i<2^{31})$，表示开始时 $S$ 中的元素。 接下来 $m$ 行每行两个整数 $opt,a$ $(1\leq opt\leq 5,0\leq a<2^{31})$，表示一次操作。保证每组测试数据中至少包含一次操作 $5$。 保证所有测试数据的 $n$ 之和不超过 $1.5\cdot10^6$，保证所有测试数据的 $m$ 之和不超过 $1.5\cdot10^6$。

Output

对于每个 $5$ 操作输出一行一个正整数，表示可重集中元素所有元素与 $a$ 按位异或运算结果的最大值。

Sample Input

1
5 10
1 2 3 4 5
5 1
1 10
5 2
2 3
5 3
3 12
5 4
4 7
5 5
5 13

Sample Output

5
8
8
12
10
14

Source

2024“钉耙编程”中国大学生算法设计超级联赛（8）