AND & OR & max on a segment#4504

AND & OR & max on a segment

1 second

128 megabytes

Medium

Vasyl has $n$ integers: $x_{1}, x_{2}, \dots, x_{n}$ x_1, x_2, \ldots, x_n. You must help him answer queries of two types:

AND L R — find the maximum value of $x_{i_{1}} AND x_{i_{2}} AND \dots AND x_{i_{k}}$ x_{i_1} \ \mathrm{AND} \ x_{i_2} \ \mathrm{AND} \ \ldots \ \mathrm{AND} \ x_{i_k}, where ${x_{i_{j}}}$ \{ x_{i_j} \} is some nonempty subset such that $L \leq i_{1} < i_{2} < \dots < i_{k} \leq R$ L \leq i_1 < i_2 < \ldots < i_k \leq R and $1 \leq L \leq R \leq n$ 1 \leq L \leq R \leq n.
OR L R — find the maximum value of $x_{i_{1}} OR x_{i_{2}} OR \dots OR x_{i_{k}}$ x_{i_1} \ \mathrm{OR} \ x_{i_2} \ \mathrm{OR} \ \ldots \ \mathrm{OR} \ x_{i_k}, where ${x_{i_{j}}}$ \{ x_{i_j} \} is some nonempty subset such that $L \leq i_{1} < i_{2} < \dots < i_{k} \leq R$ L \leq i_1 < i_2 < \ldots < i_k \leq R and $1 \leq L \leq R \leq n$ 1 \leq L \leq R \leq n.

\InputFileThe first line contains the integer $n$ ( $1 \leq n \leq 100000$ 1 \leq n \leq 100\,000). The second line contains $n$ integers $x_{i}$ x_i ( $0 \leq x_{i} \leq 1 0^{9}$ 0 \leq x_i \leq 10^9). The third line contains the integer $m$ ( $1 \leq m \leq 100000$ 1 \leq m \leq 100\,000) — the number of queries. Each of the following $m$ lines contains one query in the format described above.

\OutputFileFor each query, print the answer on a separate line.

Examples

Example 1

Loading

x_{1}, x_{2}, \dots, x_{n}

x_{i_{1}} AND x_{i_{2}} AND \dots AND x_{i_{k}}

{x_{i_{j}}}

L \leq i_{1} < i_{2} < \dots < i_{k} \leq R

1 \leq L \leq R \leq n

x_{i_{1}} OR x_{i_{2}} OR \dots OR x_{i_{k}}

{x_{i_{j}}}

L \leq i_{1} < i_{2} < \dots < i_{k} \leq R

1 \leq L \leq R \leq n

1 \leq n \leq 100000

x_{i}

0 \leq x_{i} \leq 1 0^{9}

1 \leq m \leq 100000