Codeforces Round 900 (Div. 3)--E. Iva & Pav(前缀和+二分)

Iva and Pav are a famous Serbian competitive programming couple. In Serbia, they call Pav "papuca" and that's why he will make all of Iva's wishes come true.

Iva gave Pav an array a of n elements.

Let's define f(l,r)=al & al+1 &…& ar (here && denotes the bitwise AND operation).

Note that f(l,r)is not defined when l>r.

Iva also gave Pav q queries.

Each query consists of 2 numbers, k and l, and she wants Pav to find the largest index r (l≤r≤n), such that f(l,r)≥k.

Pav wants to solve this problem fast because he doesn't want to upset Iva. He needs your help.

Input

The first line contains a single integer t (1≤t≤10^4) — the number of test cases.

The first line of each test case contains a single integer n (1≤n≤2⋅10^5) — the length of array a.

The second line of each test case contains n integers a1,a2,…,an (1≤ai≤10^9) — the elements of array a.

The third line of each test case contains a single integer q (1≤q≤10^5) — the number of queries Iva gave Pav.

The next q lines of each test case contains two numbers, l and k (1≤l≤n, 1≤k≤10^9) — the left bound for the subsegment, and the integer k described in statement.

It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5. Also, it is guaranteed that the sum of q over all test cases does not exceed 2⋅10^5.

Output

For each query output maximal index r (l≤r≤n) such that al & al+1 &…& ar ≥ k.

If such r doesn't exist, output −1.

input

3
5
15 14 17 42 34
3
1 7
2 15
4 5
5
7 5 3 1 7
4
1 7
5 7
2 3
2 2
7
19 20 15 12 21 7 11
4
1 15
4 4
7 12
5 7

output

2 -1 5 
1 5 2 2 
2 6 -1 5 

题意：给定n个数，定义f(l,r)=al & al+1 &…& ar，即区间按位与的值，给定q个询问，给定l，k，问最远的r满足f(l,r)>=k，如果不存在输出-1.

解析：根据按位与的性质可知，全一才为1，否则为0，因此，一段区间内部肯定是单调的，因此可以二分，我们可以记录一下前i个数，二进制是j的个数的前缀和，对于每个询问二分>=k的右边界即可。

#include 
using namespace std;
const int N=2e5+5;
int sum[N][35];//前i个数,二进制是j的个数
bool check(int r,int l,int k)
{
    int s=0;//总和
    for(int i=1;i<=32;i++)
    {
        if(sum[r][i]-sum[l-1][i]==r-l+1)//全1才是1
        {
            s+=1<<(i-1);
            if(s>=k) return true;//满足直接退出即可
        }
    }
    return false;
}
void solve()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int x,cnt=0;
        scanf("%d",&x);
        while(x)
        {
            sum[i][++cnt]=x%2;//
            x/=2;
        }
    }
    //累加前缀和
    for(int i=1;i<=n;i++)
        for(int j=1;j<=32;j++) sum[i][j]+=sum[i-1][j];
    int q;
    scanf("%d",&q);
    while(q--)
    {
        int l,k,ans=-1;
        scanf("%d%d",&l,&k);
        int L=l,R=n;
        //注意下写法,l和L区别
        while(L<=R)
        {
            int mid=L+R>>1;
            if(check(mid,l,k)) ans=mid,L=mid+1;
            else R=mid-1;
        }
        printf("%d ",ans);
    }
    printf("\n");
    //初始化清空
    for(int i=1;i<=n;i++)
        for(int j=1;j<=32;j++) sum[i][j]=0;
}
int main()
{
    int t=1;
    scanf("%d",&t);
    while(t--) solve();
    return 0;
}