众数

你有 $n$ 个数对 $(a_1,b_1),\ldots,(a_n,b_n)$。 定义**下标** $i(1\le i\le n)$ 的权值为将 $a_1$ 个 $b_1$，$a_2$ 个 $b_2$，...，$a_i$ 个 $b_i$ 拼接在一起后形成的数组的**最大众数**（特别地，若所有数出现次数相同则为最大数）乘以 $a_i$。 接下来你有 $m$ 个操作，分两种： - `1 x y`，将 $a_x$ 增加 $y$。**保证 $y$ 非负。** - `2 q`，求最小的正整数 $k$ 使得**下标** $n-k+1 \sim n$ 的权值异或和为 $q$。 2 操作保证有解，且所有答案之和（记为 $\sum k$）不超过 $5\times 10^7$。

输入的第一行有三个正整数 $T,n,m$，分别表示测试点编号（样例为 $0$）、数对个数和操作个数。 第二行有 $2n$ 个正整数 $a_1,b_1,a_2,b_2,\ldots,a_n,b_n$，其中第 $2i-1$ 和第 $2i$ 个数分别表示第 $i$ 个数对的 $a_i,b_i$。 之后有 $m$ 行，每行有一个操作，格式见题目描述。

对于每个 2 操作，输出一行一个正整数表示答案。

0 4 5
2 1 3 3 1 1 1 2
2 0
1 4 6
2 6
1 3 8
2 7

2
4
1

【样例解释】 最开始的四个数组为 $(2,1), (3,3),(1,1),(1,2)$。以计算下标 $2,4$ 的权值为例展示权值的计算方法： - 要计算下标 $2$ 的权值，就要把 $2$ 个 $1$、$3$ 个 $3$ 拼在一起得到 $[1,1,3,3,3]$，最大众数为 $3$；$a_2=3$，所以权值为 $3\times 3 = 9$。 - 要计算下标 $4$ 的权值，就要把 $2$ 个 $1$、$3$ 个 $3$、$1$ 个 $1$、$1$ 个 $2$ 拼在一起得 $[1,1,3,3,3,1,2]$，最大众数为 $3$；$a_4=1$，所以权值为 $3\times 1=3$。 以此类推，可知下标 $1,2,3,4$ 的权值依次为 $2,9,3,3$。当 $k=2$ 时，$3,4$ 的权值异或和 $3\oplus 3$ 恰为 $0$，符合题意。 接下来将 $a_4$ 增加 $6$ 变成 $7$，显然前 $3$ 个下标权值不变，下标 $4$ 的权值变成 $2\times 7=14$。此时所有下标权值异或和 $2\oplus 9\oplus 3\oplus 14=6$，符合题意，所以此时 $k=4$。 然后把 $a_3$ 增加 $8$ 变成 $9$。现在 $1\sim 4$ 的权值依次为 $2,9,9,7$，此时 $k=1,3$ 时对应的权值异或和都是 $7$，此时取更小的 $k$，所以输出 $1$。 【数据范围】 记 $L$ 为所有操作结束后，所有 $a_i$ 的最大值（例如样例中，$L=9$。） |测试点编号|$n,m\le$|特殊性质| |:-:|:-:|:-:| |$1\sim 2$|$30$|$a_i,y\le 30$| |$3\sim 4$|$500$|| |$5\sim 7$|$2000$|| |$8\sim 9$|$3\times 10^5$|只有 2 操作| |$10$|$3\times 10^5$|$b_i=1$| |$11\sim 12$|$3\times 10^5$|$b_i\le 2$| |$13\sim 15$|$3\times 10^5$|$\sum k\le 5\times 10^5$| |$16\sim 19$|$3\times 10^5$|$k\le 300$| |$20\sim 25$ |$3\times 10^5$|| 对于全部数据，保证 $3\le n,m\le 3\times 10^5$，且 $1\le b_i\le n$，$1\le a_i\le L\le 10^9$。 2 操作保证有解，且 $\sum k\le 5\times 10^7$。 **提示：本题读入量较大，建议选用较快的输入输出方式。**