← 返回题目列表

Codeforces · 1847/F

F. 老板的身份

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

在追踪迪亚波罗的起源时,乔鲁诺收到了波鲁纳雷夫发来的密码。该代码可以表示为正整数的无限序列:$$$a_1, a_2, \dots $$$。乔鲁诺立即看出了代码背后的规律。给出了前 $$$n$$$ 数字 $$$a_1, a_2, \dots, a_n$$$。对于 $$$i > n$$$,$$$a_i$$$ 的值为 $$$(a_{i-n}\ |\ a_{i-n+1})$$$,其中 $$$|$$$ 表示按位 OR 运算符。

有关迪亚波罗的信息隐藏在$$$q$$$问题中。每个问题都有一个与之关联的正整数 $$$v$$$,其答案是满足 $$$a_i > v$$$ 的最小索引 $$$i$$$。如果不存在这样的$$$i$$$,则答案为$$$-1$$$。帮助乔鲁诺回答问题!

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10\,000$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$ , $$$1 \leq q \leq 2 \cdot 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) - 定义模式的代码部分。

接下来的 $$$q$$$ 行中的第 $$$i$$$ 行包含一个整数 $$$v_i$$$ ($$$0 \leq v_i \leq 10^9$$$) — Giorno 问你的问题。

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

输出

打印 $$$q$$$ 数字。第 $$$i$$$ 数字是乔鲁诺提出的第 $$$i$$$ 问题的答案。

示例

输入 #1

3
2 3
2 1
1
2
3
4 5
0 2 1 3
0
1
2
3
4
5 5
1 2 3 4 5
7
2
6
0
4

输出 #1

1
3
-1
2
2
4
-1
-1
-1
3
8
1
5

注意

在第一个测试用例中,$$$a = [2,1,3,3,\ldots]$$$。

- 对于第一个问题,$$$a_1=2$$$ 是最小索引大于$$$1$$$ 的元素。
- 对于第二个问题,$$$a_3=3$$$ 是最小索引大于$$$2$$$ 的元素。
- 对于第三个问题,没有索引 $$$i$$$ 使得 $$$a_i > 3$$$。