MinimizOR solution codeforces

You are given an array

a

n

non-negative integers, numbered from

1

n

. Let’s define the cost of the array

a

min_{i \neq j} a_{i} | a_{j}

, where

|

denotes the bitwise OR operation. There are

q

queries. For each query you are given two integers

l

and

r

(

l < r

). For each query you should find the cost of the subarray

a_{l}, a_{l + 1}, \dots, a_{r}

Input

Each test case consists of several test cases. The first line contains a single integer

t

(

1 \leq t \leq 10^{4}

) — the number of test cases. The first line of each test case contains an integer

n

(

2 \leq n \leq 10^{5}

) — the length array

a

. The second line of each test case contains

n

integers

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

(

0 \leq a_{i} < 2^{30}

) — the elements of

a

. The third line of each test case contains an integer

q

(

1 \leq q \leq 10^{5}

) — the number of queries. Each of the next

q

lines contains two integers

l_{j}

r_{j}

(

1 \leq l_{j} < r_{j} \leq n

) — the description of the

j

-th query. It is guaranteed that the sum of

n

and the sum of

q

over all test cases do not exceed

10^{5}

Output

For each test case print

q

numbers, where the

j

-th number is the cost of array

a_{l_{j}}, a_{l_{j} + 1}, \dots, a_{r_{j}}

Example

input

Copy

2
5
6 1 3 2 1
4
1 2
2 3
2 4
2 5
4
0 2 1 1073741823
4
1 2
2 3
1 3
3 4

output

Copy

Note

In the first test case the array

a

110_{2}, 001_{2}, 011_{2}, 010_{2}, 001_{2}

. That’s why the answers for the queries are:

$[1; 2]$ : $a_{1} | a_{2} = 110_{2} | 001_{2} = 111_{2} = 7$ ;
$[2; 3]$ : $a_{2} | a_{3} = 001_{2} | 011_{2} = 011_{2} = 3$ ;
$[2; 4]$ : $a_{2} | a_{3} = a_{3} | a_{4} = a_{2} | a_{4} = 011_{2} = 3$ ;
$[2; 5]$ : $a_{2} | a_{5} = 001_{2} = 1$ .

In the second test case the array

a

00_{2}, 10_{2}, 01_{2}, \underset{30}{\underset{⏟}{11 \dots 1_{2}}}

(

a_{4} = 2^{30} - 1

). That’s why the answers for the queries are:

$[1; 2]$ : $a_{1} | a_{2} = 10_{2} = 2$ ;
$[2; 3]$ : $a_{2} | a_{3} = 11_{2} = 3$ ;
$[1; 3]$ : $a_{1} | a_{3} = 01_{2} = 1$ ;
$[3; 4]$ : $a_{3} | a_{4} = 01_{2} | \underset{30}{\underset{⏟}{11 \dots 1_{2}}} = 2^{30} - 1 = 1073741823$ .
ANSWER

“Click Here“

MinimizOR solution codeforces

ANSWER

“Click Here“

Leave a Comment Cancel reply