AND & OR & max on a segment

Vasyl has n integers: x[1], x[2],..., x[n]. You must help him to answer the queries of two types:

1. AND L R - in this case find the maximum value x[i1] AND x[i2] AND ... AND x[ik], where {x[ik]} is some nonempty subset, L ≤ i[1] < i[2] < ... < i[k] ≤ R, 1 ≤ L ≤ R ≤ n.

2. OR L R - in this case find the maximum value x[i1] OR x[i2] OR ... OR x[ik], where {x[ik]} is some nonempty subset, L ≤ i[1] < i[2] < ... < i[k] ≤ R, 1 ≤ L ≤ R ≤ n.

Input

The first line contains number n (1 ≤ n ≤ 100000). Next line contains n numbers x[i] (0 ≤ x[i] ≤ 10^9). Then the number of queries m (1 ≤ m ≤ 10^5) is given. Each of the next m lines contains one query.

Output

For each query print the answer in separate line.

Examples