给你两个数组 $$$a$$$ 和 $$$b$$$,大小为 $$$n$$$ 以及一个固定整数 $$$v$$$。
如果 $$$(b_l \mid b_{l+1} \mid \ldots \mid b_r) \ge v$$$ 则称区间 $$$[l, r]$$$ 为良好区间,其中 $$$|$$$ 表示按位 OR 运算。好的区间之美定义为 $$$\max(a_l, a_{l+1}, \ldots, a_r)$$$。
您将获得两种类型的 $$$q$$$ 查询:
- "1 i x": 赋值 $$$b_i := x$$$;
- “2 l r”:在所有好的区间 $$$[l_0,r_0]$$$ 中找到满足 $$$l \le l_0 \le r_0 \le r$$$ 的最小美度。如果没有合适的好区间,则输出$$$-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, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。
每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 10^9$$$)。
每个测试用例的第四行包含一个整数 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$)。
以下 $$$q$$$ 行中的第 $$$i$$$ 行包含查询的描述。每条线都属于以下两种类型之一:
- "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$$$。
输出
对于每个测试用例,输出第二类型的所有查询的答案。
示例
输入 #1
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
-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$$$,小于 $$$v$$$。因此,不存在良好的区间。
第二个查询要求将 $$$b_2$$$ 更改为 $$$5$$$,因此 $$$b$$$ 变为 $$$[2, 5, 3]$$$。
第三个查询属于第二种类型,$$$l = 2$$$ 且 $$$r = 3$$$。存在三种可能的间隔:$$$[2, 2]$$$、$$$[3, 3]$$$ 和 $$$[2, 3]$$$。然而,$$$b_2 = 5 < v$$$,$$$b_3 = 3 < v$$$。所以只有最后一个间隔是好的:它有 $$$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$$$、$$$5$$$。因此答案是$$$5$$$。