← 返回题目列表

Codeforces · 1878/E

E. 伊娃和帕夫

中文机器翻译题面 查看原题

Iva 和 Pav 是塞尔维亚著名的竞技编程情侣。在塞尔维亚,他们称帕夫为“papuca”,这就是为什么他会让伊娃的所有愿望成真。

Iva 给了 Pav 一个包含 $$$n$$$ 元素的数组 $$$a$$$。

我们定义 $$$f(l, r) = a_l \ \& \ a_{l+1} \ \& \dots \& \ a_r$$$ (这里 $$$\&$$$ 表示按位 AND 运算)。

请注意,当 $$$l>r$$$ 时,$$$f(l, r)$$$ 未定义。

Iva 还向 Pav 提出了 $$$q$$$ 查询。

每个查询由 2 个数字组成,$$$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

注意

在第一个测试用例 $$$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$$$ 不存在,所以答案是 $$$-1$$$。

第三个查询要求 $$$f(4, r) \ge 5$$$。 $$$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$$$。