Problems
AND & OR & max on a segment
AND & OR & max on a segment
Vasyl has n integers: x1
, x2
,..., xn
. You must help him to answer the queries of two types:
- AND L R - in this case find the maximum value
xi1
ANDxi2
AND ... ANDxik
, where {xik
} is some nonempty subset, L ≤i1
<i2
< ... <ik
≤ R, 1 ≤ L ≤ R ≤ n. - OR L R - in this case find the maximum value
xi1
ORxi2
OR ... ORxik
, 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 ≤ 105
) is given. Each of the next m lines contains one query.
Output
For each query print the answer in separate line.
Input example #1
5 1 2 3 4 5 10 AND 1 5 AND 1 4 AND 1 3 AND 2 4 AND 1 1 OR 1 5 OR 1 1 OR 1 2 OR 1 3 OR 4 5
Output example #1
5 4 3 4 1 7 1 3 3 5