Vasyl has n integers: x[1]
, x[2]
,..., x[n]
. You must help him to answer the queries of two types:
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.
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.
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.
For each query print the answer in separate line.