eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

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

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

  1. AND L R - в этом случае нужно найти маскимальное значение x[i1] AND x[i2] AND ... AND x[ik], где {x[ik]} - некоторое непустое подмножество, Li[1] < i[2] < ... < i[k]R, 1LRn.

  2. OR L R - в этом случае вам нужно найти маскимальное значение x[i1] OR x[i2] OR ... OR x[ik], где {x[ik]} - некоторое непустое подмножество, Li[1] < i[2] < ... < i[k]R, 1LRn.

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

В первой строке задано число n (1n10^5).

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

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

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

Пример

Входные данные #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
5
4
3
4
1
7
1
3
3
5
Автор Владимир Чих
Источник Дистанционная Летняя Компьютерная Школа - лето 2013 года