A6883 · Iva & Pav · GESP考级

题目描述

Iva 和 Pav 是塞尔维亚著名的竞赛编程情侣。在塞尔维亚，人们称 Pav 为“papuca”，因此他会满足 Iva 的所有愿望。 Iva 给了 Pav 一个长度为 $n$ 的数组 $a$。 我们定义 $f(l, r) = a_l \ \& \ a_{l+1} \ \& \dots \& \ a_r$（这里 $ \& $ 表示[按位与运算](http://tiny.cc/bitwise_and)）。 注意，当 $l > r$ 时，$f(l, r)$ 没有定义。 Iva 还给了 Pav $q$ 个询问。 每个询问包含两个数字 $k$ 和 $l$，她希望 Pav 找出最大的下标 $r$（$l \le r \le n$），使得 $f(l, r) \ge k$。 Pav 想要尽快解决这个问题，因为他不想让 Iva 不高兴。他需要你的帮助。

第一行包含一个整数 $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$。

对于每个询问，输出最大的下标 $r$（$l \le r \le n$），使得 $a_l \ \& \ a_{l+1} \ \& \dots \& \ a_r \ge k$。 如果不存在这样的 $r$，输出 $-1$。

输入 #1

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

输出 #1

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