Vasyl has n integers: x1, x2,..., xn. You must help him to answer the queries of two types:

1. AND L R - in this case find the minimum value xi1 AND xi2 AND ... AND xik, where {xik} is some nonempty subset, L ≤ i1 < i2 < ... < ik ≤ R, 1 ≤ L ≤ R ≤ n.
2. OR L R - in this case find the minimum value xi1 OR xi2 OR ... OR xik, where {xik} is some nonempty subset, L ≤ i1 < i2 < ... < ik ≤ R, 1 ≤ L ≤ R ≤ n.

Input

The first line contains number n (1 ≤ n ≤ 100000). Next line contains n numbers xi (0 ≤ xi ≤ 109). Then the number of queries m (1 ≤ m ≤ 100000) is given. Each of the next m lines contains one query.

Output

For each query print the answer in separate line.