AND & OR & max на отрезке

У Василия есть n чисел: x[1], x[2],..., x[n].

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

1. 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.

2. 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 ≤ 10^5).

В следующей строке задано n чисел x[i] (0 ≤ x[i] ≤ 10^9). После этого задано число m (1 ≤ m ≤ 10^5) - количество запросов, на которые вам нужно найти ответ. В последующих m сроках заданы сами запросы.

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

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

Примеры