D. Битовый парадокс
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Даны два массива целых чисел $$$a$$$ и $$$b$$$ длины $$$n$$$, а также фиксированное целое число $$$v$$$.

Отрезок $$$[l, r]$$$ назовём хорошим, если $$$(b_l \mid b_{l+1} \mid \ldots \mid b_r) \ge v$$$, где $$$|$$$ обозначает операцию побитового ИЛИ. Далее, красота хорошего отрезка определяется как $$$\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$$$).

В $$$i$$$-й из следующих $$$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$$$, что меньше $$$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$$$.