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$$$。