У Василия есть n чисел: x1, x2,..., xn. Вы должны помочь ему быстрко отвечать на запросы двух типов:

1. AND L R - здесь вам нужно найти минимальное значение xi1 AND xi2 AND ... AND xik, где {xik} - некоторое непустое подмножество, L ≤ i1 < i2 < ... < ik ≤ R, 1 ≤ L ≤ R ≤ n.
2. OR L R - в этом случае вам нужно найти минимальное значение xi1 OR xi2 OR ... OR xik, где {xik} - некоторое непустое подмножество, L ≤ i1 < i2 < ... < ik ≤ R, 1 ≤ L ≤ R ≤ n.

Входные данные

В первой строке задано число n (1 ≤ n ≤ 100000). В следующей строке задано n чисел xi (0 ≤ xi ≤ 109). После этого задано количество запросов m (1 ≤ m ≤ 100000), на которые Вам нужно найти ответ. В последующих m строках заданы сами запросы.

Выходные данные

Ответ на каждый запрос выводите в новой строке.