У Василия есть n чисел: x[1]
, x[2]
,..., x[n]
. Вы должны помочь ему быстрко отвечать на запросы двух типов:
AND L R - здесь вам нужно найти минимальное значение x[i1]
AND x[i2]
AND ... AND x[ik]
, где {x[ik]
} - некоторое непустое подмножество, L ≤ i[1]
< i[2]
< ... < i[k]
≤ R, 1 ≤ L ≤ R ≤ n.
OR L R - в этом случае вам нужно найти минимальное значение x[i1]
OR x[i2]
OR ... OR x[ik]
, где {x[ik]
} - некоторое непустое подмножество, L ≤ i[1]
< i[2]
< ... < i[k]
≤ R, 1 ≤ L ≤ R ≤ n.
В первой строке задано число n (1 ≤ n ≤ 100000). В следующей строке задано n чисел x[i]
(0 ≤ x[i]
≤ 10^9
). После этого задано количество запросов m (1 ≤ m ≤ 100000), на которые Вам нужно найти ответ. В последующих m строках заданы сами запросы.
Ответ на каждый запрос выводите в новой строке.