Chef Geonggongi

Time limit2sMemory limit1024 MB

Summary

Given N values up to 511, answer Q range queries: the maximum of (XOR of a chosen subset in the range) plus the subset size.

Level: Medium6 of 10
Topics: Bit manipulation, Dynamic programming, Array
Solved: No attempts yet

Problem

Did you know that Geonggongi is a remarkably skilled chef? Geonggongi can make the most delicious dish from any set of ingredients.

Geonggongi has $N$ ingredients, numbered from $1$ to $N$ . Ingredient $i$ has a flavor value of $T_i$ . The flavor of a dish Geonggongi makes is (XOR of the flavors of all used ingredients) + (number of used ingredients).

There are $Q$ queries, each given as $l$ and $r$ . For each query, find the maximum flavor of a dish Geonggongi can make using zero or more of the ingredients from the $l$ -th through the $r$ -th ( $r - l + 1$ ingredients).

Input

The first line contains $N$ ( $1 \leq N \leq 500$ ).

The second line contains $N$ flavor values $T_1, T_2, \cdots, T_N$ , separated by spaces ( $0 \leq T_i \leq 511$ ).

The third line contains $Q$ ( $1 \leq Q \leq 100\ 000$ ).

Each of the next $Q$ lines contains $l$ and $r$ , separated by a space ( $1 \leq l \leq r \leq N$ ).

Output

Print $Q$ lines. For each query, print the maximum flavor of a dish Geonggongi can make, one per line.

Examples1

Example 1

Input

8
1 2 3 4 5 6 7 8
5
1 1
2 4
4 8
5 6
3 4

Expected output