AND & OR & min на відрізку

У Василька є 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 ≤ 100000. У наступних M рядках задано самі запити.

Вихідні дані

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

Приклади