311123: CF1937F. Bitwise Paradox

F. Bitwise Paradoxtime limit per test5 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

You are given two arrays $a$ and $b$ of size $n$ along with a fixed integer $v$.

An interval $[l, r]$ is called a good interval if $(b_l \mid b_{l+1} \mid \ldots \mid b_r) \ge v$, where $|$ denotes the bitwise OR operation. The beauty of a good interval is defined as $\max(a_l, a_{l+1}, \ldots, a_r)$.

You are given $q$ queries of two types:

• "1 i x": assign $b_i := x$;
• "2 l r": find the minimum beauty among all good intervals $[l_0,r_0]$ satisfying $l \le l_0 \le r_0 \le r$. If there is no suitable good interval, output $-1$ instead.

Please process all queries.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $v$ ($1 \le n \le 2 \cdot 10^5$, $1 \le v \le 10^9$).

The second line of each testcase contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$).

The third line of each testcase contains $n$ integers $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 10^9$).

The fourth line of each testcase contains one integer $q$ ($1 \le q \le 2 \cdot 10^5$).

The $i$-th of the following $q$ lines contains the description of queries. Each line is of one of two types:

• "1 i x" ($1 \le i \le n$, $1 \le x \le 10^9)$;
• "2 l r" ($1 \le l \le r \le n$).

It is guaranteed that both the sum of $n$ and the sum of $q$ over all test cases do not exceed $2 \cdot 10^5$.

Output

For each test case, output the answers for all queries of the second type.

ExampleInput

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

Output

-1 3 2 
5 2 2 1 
-1 

Note

In the first test case, $a = [2, 1, 3]$, $b = [2, 2, 3]$, and $v = 7$.

The first query is of the second type and has $l = 1$ and $r = 3$. The largest interval available is $[1, 3]$, and its bitwise OR is $b_1 \mid b_2 \mid b_3 = 3$ which is less than $v$. Thus, no good interval exists.

The second query asks to change $b_2$ to $5$, so $b$ becomes $[2, 5, 3]$.

The third query is of the second type and has $l = 2$ and $r = 3$. There are three possible intervals: $[2, 2]$, $[3, 3]$, and $[2, 3]$. However, $b_2 = 5 < v$, $b_3 = 3 < v$. So only the last interval is good: it has $b_2 \mid b_3 = 7$. The answer is thus $\max(a_2, a_3) = 3$.

The fourth query is of the second type and has $l = 1$ and $r = 3$. There are three good intervals: $[1, 2]$, $[2, 3]$, and $[1, 3]$. Their beauty is $2$, $3$, $3$ correspondingly. The answer is thus $2$.

In the second test case, $a = [5, 1, 2, 4]$, $b = [4, 2, 3, 3]$, and $v = 5$.

The first query has $l = 1$ and $r = 4$. The only good intervals are: $[1, 2]$, $[1, 3]$, $[1, 4]$. Their beauty is $5$, $5$, $5$ correspondingly. The answer is thus $5$.

题目大意：
给定两个长度为n的数组a和b，以及一个固定整数v。如果区间[l, r]满足(b_l | b_{l+1} | ... | b_r) >= v，其中|表示按位或操作，则称该区间为“好区间”。一个“好区间”的“美感”定义为max(a_l, a_{l+1}, ..., a_r)。

有q个查询，分为两种类型：
1. "1 i x"：将b_i赋值为x；
2. "2 l r"：找出所有满足l <= l_0 <= r_0 <= r的“好区间”[l_0,r_0]中的最小“美感”。如果没有合适的“好区间”，则输出-1。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1 <= t <= 10^5），表示测试用例的数量。
- 每个测试用例的描述如下：
- 第一行包含两个整数n和v（1 <= n <= 2 * 10^5，1 <= v <= 10^9）。
- 第二行包含n个整数a_1, a_2, ..., a_n（1 <= a_i <= 10^9）。
- 第三行包含n个整数b_1, b_2, ..., b_n（1 <= b_i <= 10^9）。
- 第四行包含一个整数q（1 <= q <= 2 * 10^5）。
- 接下来的q行包含查询的描述。每行是以下两种类型之一：
- "1 i x"（1 <= i <= n，1 <= x <= 10^9）；
- "2 l r"（1 <= l <= r <= n）。
- 保证所有测试用例的n和q之和不超过2 * 10^5。

输出：
- 对于每个测试用例，输出所有第二种类型查询的答案。题目大意： 给定两个长度为n的数组a和b，以及一个固定整数v。如果区间[l, r]满足(b_l | b_{l+1} | ... | b_r) >= v，其中|表示按位或操作，则称该区间为“好区间”。一个“好区间”的“美感”定义为max(a_l, a_{l+1}, ..., a_r)。 有q个查询，分为两种类型： 1. "1 i x"：将b_i赋值为x； 2. "2 l r"：找出所有满足l <= l_0 <= r_0 <= r的“好区间”[l_0,r_0]中的最小“美感”。如果没有合适的“好区间”，则输出-1。 输入输出数据格式： 输入： - 第一行包含一个整数t（1 <= t <= 10^5），表示测试用例的数量。 - 每个测试用例的描述如下： - 第一行包含两个整数n和v（1 <= n <= 2 * 10^5，1 <= v <= 10^9）。 - 第二行包含n个整数a_1, a_2, ..., a_n（1 <= a_i <= 10^9）。 - 第三行包含n个整数b_1, b_2, ..., b_n（1 <= b_i <= 10^9）。 - 第四行包含一个整数q（1 <= q <= 2 * 10^5）。 - 接下来的q行包含查询的描述。每行是以下两种类型之一： - "1 i x"（1 <= i <= n，1 <= x <= 10^9）； - "2 l r"（1 <= l <= r <= n）。 - 保证所有测试用例的n和q之和不超过2 * 10^5。 输出： - 对于每个测试用例，输出所有第二种类型查询的答案。