时间限制：每个测试点 5 秒
内存限制：每个测试点 1024 MB

给定两个长度为 $n$ 的数组 $a$ 和 $b$，以及一个固定的整数 $v$。

如果一个区间 $[l, r]$ 满足 $(b_l \mid b_{l+1} \mid \dots \mid b_r) \ge v$（其中 $\mid$ 表示按位或运算），则称其为 好区间。好区间的 优美值 定义为 $\max(a_l, a_{l+1}, \dots, a_r)$。

你会收到 $q$ 个查询，分为两种类型：

• 1 i x：将 $b_i$ 赋值为 $x$；
• 2 l r：求所有满足 $l \le l_0 \le r_0 \le r$ 的好区间 $[l_0, r_0]$ 中，最小的优美值。如果不存在这样的好区间，输出 $-1$。

请处理所有查询。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^5$）。接下来是每个测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $v$（$1 \le n \le 2 \cdot 10^5$，$1 \le v \le 10^9$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）。

第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$1 \le b_i \le 10^9$）。

第四行包含一个整数 $q$（$1 \le q \le 2 \cdot 10^5$）。

接下来的 $q$ 行，每行描述一个查询。每行的格式为以下两种之一：

• 1 i x（$1 \le i \le n$，$1 \le x \le 10^9$）；
• 2 l r（$1 \le l \le r \le n$）。

保证所有测试用例的 $n$ 之和以及 $q$ 之和均不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，按顺序输出所有第二类查询的答案。

示例

输入

3
3 7
2 1 3
2 2 3
4
2 1 3
1 2 5
2 2 3
2 1 3
4 5
5 1 2 4
4 2 3 3
6
2 1 4
1 3 15
2 3 4
2 2 4
1 2 13
2 1 4
1 5
6
4
1
2 1 1

输出

-1 3 2
5 2 2 1
-1

说明

第一个测试用例：
$a = [2, 1, 3],\ b = [2, 2, 3],\ v = 7$。

• 第一个查询（第二类）：$l = 1,\ r = 3$。最大的区间是 $[1, 3]$，其按位或为 $b_1 \mid b_2 \mid b_3 = 3 < 7$，因此不存在好区间。
• 第二个查询：将 $b_2$ 改为 $5$，此时 $b = [2, 5, 3]$。
• 第三个查询（第二类）：$l = 2,\ r = 3$。可能的区间有 $[2, 2],\ [3, 3],\ [2, 3]$。但 $b_2 = 5 < 7$，$b_3 = 3 < 7$，只有区间 $[2, 3]$ 是好区间：$b_2 \mid b_3 = 7$。答案为 $\max(a_2, a_3) = 3$。
• 第四个查询（第二类）：$l = 1,\ r = 3$。存在三个好区间：$[1, 2],\ [2, 3],\ [1, 3]$，其优美值分别为 $2,\ 3,\ 3$，因此答案为 $2$。

第二个测试用例：
$a = [5, 1, 2, 4],\ b = [4, 2, 3, 3],\ v = 5$。

• 第一个查询（第二类）：$l = 1,\ r = 4$。好区间有 $[1, 2],\ [1, 3],\ [1, 4]$，优美值均为 $5$，答案为 $5$。
  ……（后续类似）