Даны два массива целых чисел \(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\).
Обработайте все запросы.
Примечание
В первом наборе входных данных \(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\).