MinimizOR solution codeforces

MinimizOR solution codeforces

 
You are given an array aa of nn non-negative integers, numbered from 11 to nn. Let’s define the cost of the array aa as minijai|ajmini≠jai|aj, where || denotes the bitwise OR operation. There are qq queries. For each query you are given two integers ll and rr (l<rl<r). For each query you should find the cost of the subarray al,al+1,,aral,al+1,…,ar.
Input
Each test case consists of several test cases. The first line contains a single integer tt (1t1041≤t≤104) — the number of test cases. The first line of each test case contains an integer nn (2n1052≤n≤105) — the length array aa. The second line of each test case contains nn integers a1,a2,,ana1,a2,…,an (0ai<2300≤ai<230) — the elements of aa. The third line of each test case contains an integer qq (1q1051≤q≤105) — the number of queries. Each of the next qq lines contains two integers ljljrjrj (1lj<rjn1≤lj<rj≤n) — the description of the jj-th query. It is guaranteed that the sum of nn and the sum of qq over all test cases do not exceed 105105.
Output
For each test case print qq numbers, where the jj-th number is the cost of array alj,alj+1,,arjalj,alj+1,…,arj.
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
7
3
3
1
2
3
1
1073741823
Note
In the first test case the array aa is 1102,0012,0112,0102,00121102,0012,0112,0102,0012. That’s why the answers for the queries are:
  • [1;2][1;2]a1|a2=1102|0012=1112=7a1|a2=1102|0012=1112=7;
  • [2;3][2;3]a2|a3=0012|0112=0112=3a2|a3=0012|0112=0112=3;
  • [2;4][2;4]a2|a3=a3|a4=a2|a4=0112=3a2|a3=a3|a4=a2|a4=0112=3;
  • [2;5][2;5]a2|a5=0012=1a2|a5=0012=1.
In the second test case the array aa is 002,102,012,111230002,102,012,11…12⏟30 (a4=2301a4=230−1). That’s why the answers for the queries are:
  • [1;2][1;2]a1|a2=102=2a1|a2=102=2;
  • [2;3][2;3]a2|a3=112=3a2|a3=112=3;
  • [1;3][1;3]a1|a3=012=1a1|a3=012=1;
  • [3;4][3;4]a3|a4=012|111230=2301=1073741823a3|a4=012|11…12⏟30=230−1=1073741823.
  • ANSWER

    Click Here

Leave a Comment