Задачи
AND & OR & min на отрезке
AND & OR & min на отрезке
У Василия есть n чисел: x1
, x2
,..., xn
. Вы должны помочь ему быстрко отвечать на запросы двух типов:
- AND L R - здесь вам нужно найти минимальное значение
xi1
ANDxi2
AND ... ANDxik
, где {xik
} - некоторое непустое подмножество, L ≤i1
<i2
< ... <ik
≤ R, 1 ≤ L ≤ R ≤ n. - OR L R - в этом случае вам нужно найти минимальное значение
xi1
ORxi2
OR ... ORxik
, где {xik
} - некоторое непустое подмножество, L ≤i1
<i2
< ... <ik
≤ R, 1 ≤ L ≤ R ≤ n.
Входные данные
В первой строке задано число n (1 ≤ n ≤ 100000). В следующей строке задано n чисел xi
(0 ≤ xi
≤ 109
). После этого задано количество запросов m (1 ≤ m ≤ 100000), на которые Вам нужно найти ответ. В последующих m строках заданы сами запросы.
Выходные данные
Ответ на каждый запрос выводите в новой строке.
Входные данные #1
5 1 2 3 4 5 4 AND 1 5 OR 1 5 AND 1 1 OR 3 4
Выходные данные #1
0 1 1 3