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 ≤ 100000).

У наступному рядку задано n чисел x[i] (0 ≤ x[i] ≤ 10^9). Після цього задано число m (1 ≤ m ≤ 10^5) - кількість запитів, на які вам потрібно знайти відповідь. У наступних m рядках задано самі запити.

Вихідні дані

Відповідь на кожен запит виводьте в новому рядку.

Приклади