题目描述

你有 $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$，Hack 数据是 $26\sim 100$ 之间的自然数）、数对个数和操作个数。

第二行有 $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$。）

对于全部数据，保证 $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$。

提示：本题读入量较大，建议选用较快的输入输出方式。