CF1878E.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) = a_l \ \& \ a_{l+1} \ \& \dots \& \ a_r$ (here $\&$ denotes the bitwise AND operation).

Note that $f(l, r)$ is not defined when $l \gt 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 \le r \le n$), such that $f(l, r) \ge k$.

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

伊娃和帕夫是一对著名的塞尔维亚竞赛编程情侣。在塞尔维亚，人们称帕夫为“papuca”，因此他将实现伊娃的所有愿望。

伊娃给了帕夫一个包含 $n$ 个元素的数组 $a$。

我们定义 $f(l, r) = a_l \ \& \ a_{l+1} \ \& \dots \& \ a_r$（此处 $\&$ 表示按位与运算）。

注意：当 $l \gt r$ 时，$f(l, r)$ 未定义。

伊娃还给了帕夫 $q$ 个查询。

每个查询包含两个数 $k$ 和 $l$，她希望帕夫找出满足 $f(l, r) \ge k$ 的最大下标 $r$（其中 $l \le r \le n$）。

帕夫希望快速解决这个问题，以免让伊娃不高兴。他需要你的帮助。

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

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

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the elements of array $a$.

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

The next $q$ lines of each test case contains two numbers, $l$ and $k$ ($1 \le l \le n$, $1 \le k \le 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 \cdot 10^5$. Also, it is guaranteed that the sum of $q$ over all test cases does not exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 数组 $a$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）—— 数组 $a$ 的元素。

每个测试用例的第三行包含一个整数 $q$（$1 \le q \le 10^5$）—— Iva 给 Pav 的查询数量。

每个测试用例接下来的 $q$ 行，每行包含两个数 $l$ 和 $k$（$1 \le l \le n$，$1 \le k \le 10^9$）—— 子段的左边界，以及题目描述中所述的整数 $k$。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。同时，保证所有测试用例的 $q$ 之和不超过 $2 \cdot 10^5$。

For each query output maximal index $r$ ($l \le r \le n$) such that $a_l \ \& \ a_{l+1} \ \& \dots \& \ a_r \ \ge \ k$.

If such $r$ doesn't exist, output $-1$.

对于每个查询，输出最大的索引 $r$（满足 $l \le r \le n$），使得 $a_l \ \& \ a_{l+1} \ \& \dots \& \ a_r \ \ge \ k$。

如果这样的 $r$ 不存在，则输出 $-1$。

In the first test case $n=5$, and the array $a = [15, 14, 17, 42, 34]$

The first query asks for the biggest index $r$ such that the $f(1, r) \ge 7$.

$f(1,1) = 15, \ f(1, 2) = 14, \ f(1,3)=0 \ f(1, 4)=0 \ f(1, 5)=0$, so $r=2$ is the answer.

The second query asks for $f(2, r) \ge 15$. Since such $r$ doesn't exist, the answer is $-1$.

The third query asks for $f(4, r) \ge 5$. $f(4, 4) = 42, \ f(4, 5) = 34$, so $r=5$ is the answer.

In the second test case $n=5$, and the array $a= [7, 5, 3, 1, 7]$.

For the first query, $f(1, r) \ge 7$.

$f(1, 1)=7, \ f(1, 2)=5, \ f(1, 3) = 1, \ f(1,4) = 1, \ f(1, 5)=1$, so the answer to this query is $1$.

For the second query, $f(5, r) \ge 7$.

$f(5, 5) = 7$, so the answer is $5$.

For the third query, $f(2, r) \ge 3$.

$f(2, 2) = 5, \ f(2, 3) = 1, \ f(2, 4) = 1, \ f(2, 5) = 1$, so the answer is $2$.

第一个测试用例中，$n=5$，数组 $a = [15, 14, 17, 42, 34]$。

第一个查询要求找出最大的下标 $r$，使得 $f(1, r) \ge 7$。

$f(1,1) = 15,\ f(1, 2) = 14,\ f(1,3)=0,\ f(1, 4)=0,\ f(1, 5)=0$，因此答案为 $r=2$。

第二个查询要求找出满足 $f(2, r) \ge 15$ 的 $r$。由于不存在这样的 $r$，答案为 $-1$。

第三个查询要求找出满足 $f(4, r) \ge 5$ 的 $r$。$f(4, 4) = 42,\ f(4, 5) = 34$，因此答案为 $r=5$。

第二个测试用例中，$n=5$，数组 $a= [7, 5, 3, 1, 7]$。

对于第一个查询，要求满足 $f(1, r) \ge 7$。

$f(1, 1)=7,\ f(1, 2)=5,\ f(1, 3) = 1,\ f(1,4) = 1,\ f(1, 5)=1$，因此该查询的答案为 $1$。

对于第二个查询，要求满足 $f(5, r) \ge 7$。

$f(5, 5) = 7$，因此答案为 $5$。

对于第三个查询，要求满足 $f(2, r) \ge 3$。

$f(2, 2) = 5,\ f(2, 3) = 1,\ f(2, 4) = 1,\ f(2, 5) = 1$，因此答案为 $2$。