AND & OR & max на отрезке - Задачи

У Василия есть n чисел: x₁, x₂,..., x_n.

Вы должны помочь ему быстро отвечать на запросы двух типов:

AND L R - в этом случае нужно найти маскимальное значение x_i1 AND x_i2 AND ... AND x_ik, где {x_ik} - некоторое непустое подмножество, L ≤ i₁ < i₂ < ... < i_k ≤ R, 1 ≤ L ≤ R ≤ n.
OR L R - в этом случае вам нужно найти маскимальное значение x_i1 OR x_i2 OR ... OR x_ik, где {x_ik} - некоторое непустое подмножество, L ≤ i₁ < i₂ < ... < i_k ≤ R, 1 ≤ L ≤ R ≤ n.

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

В первой строке задано число n (1 ≤ n ≤ 10⁵).

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

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

Выведите ответ для каждого запроса в отдельной строке.

Лимит времени 1 секунда

Лимит использования памяти 128 MiB

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

5
1 2 3 4 5
10
AND 1 5
AND 1 4
AND 1 3
AND 2 4
AND 1 1
OR 1 5
OR 1 1
OR 1 2
OR 1 3
OR 4 5

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

Автор Владимир Чих

Источник Дистанционная Летняя Компьютерная Школа - лето 2013 года