310534: CF1847F. The Boss's Identity

F. The Boss's Identitytime limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

While tracking Diavolo's origins, Giorno receives a secret code from Polnareff. The code can be represented as an infinite sequence of positive integers: $a_1, a_2, \dots $. Giorno immediately sees the pattern behind the code. The first $n$ numbers $a_1, a_2, \dots, a_n$ are given. For $i > n$ the value of $a_i$ is $(a_{i-n}\ |\ a_{i-n+1})$, where $|$ denotes the bitwise OR operator.

Pieces of information about Diavolo are hidden in $q$ questions. Each question has a positive integer $v$ associated with it and its answer is the smallest index $i$ such that $a_i > v$. If no such $i$ exists, the answer is $-1$. Help Giorno in answering the questions!

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10\,000$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $q$ ($2 \leq n \leq 2 \cdot 10^5$ , $1 \leq q \leq 2 \cdot 10^5$).

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0 \leq a_i \leq 10^9$) — the parts of the code which define the pattern.

The $i$-th line of the next $q$ lines contain a single integer $v_i$ ($0 \leq v_i \leq 10^9$) — the question Giorno asks you.

The sum of $n$ and $q$ over all test cases does not exceed $2 \cdot 10^5$.

Output

Print $q$ numbers. The $i$-th number is the answer to the $i$-th question asked by Giorno.

ExampleInput

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

Output

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

Note

In the first test case, $a = [2,1,3,3,\ldots]$.

• For the first question, $a_1=2$ is the element with the smallest index greater than $1$.
• For the second question, $a_3=3$ is the element with the smallest index greater than $2$.
• For the third question, there is no index $i$ such that $a_i > 3$.

题目大意：
老板的身份
在追踪迪亚波罗的起源时，乔鲁诺从波纳雷夫那里收到了一个密码。这个密码可以表示为一个无限的正整数序列：a1，a2，…。乔鲁诺立即看出了代码背后的模式。给定的前n个数a1，a2，…，an。对于i>n，ai的值是(ai-n | ai-n+1)，其中|表示按位或运算符。
有关迪亚波罗的信息隐藏在q个问题中。每个问题都与一个正整数v相关联，其答案是满足ai>v的最小索引i。如果没有这样的i，答案是-1。帮助乔鲁诺回答问题！

输入数据格式：
每个测试包含多个测试用例。第一行包含测试用例数t（1≤t≤10000）。接下来是测试用例的描述。
每个测试用例的第一行包含两个整数n和q（2≤n≤2*10^5，1≤q≤2*10^5）。
每个测试用例的第二行包含n个整数a1，a2，…，an（0≤ai≤10^9）——定义模式的代码部分。
接下来的q行中的第i行包含一个整数vi（0≤vi≤10^9）——乔鲁诺问你一个问题。
所有测试用例的n和q之和不超过2*10^5。

输出数据格式：
打印q个数字。第i个数是乔鲁诺提出的第i个问题的答案。

示例：
输入：
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
3
-1
2
2
4
-1
-1
-1
3
8
1
5

注意：
在第一个测试用例中，a=[2,1,3,3,…]。
- 对于第一个问题，a1=2是索引大于1的最小元素。
- 对于第二个问题，a3=3是索引大于2的最小元素。
- 对于第三个问题，没有索引i使得ai>3。题目大意： 老板的身份 在追踪迪亚波罗的起源时，乔鲁诺从波纳雷夫那里收到了一个密码。这个密码可以表示为一个无限的正整数序列：a1，a2，…。乔鲁诺立即看出了代码背后的模式。给定的前n个数a1，a2，…，an。对于i>n，ai的值是(ai-n | ai-n+1)，其中|表示按位或运算符。 有关迪亚波罗的信息隐藏在q个问题中。每个问题都与一个正整数v相关联，其答案是满足ai>v的最小索引i。如果没有这样的i，答案是-1。帮助乔鲁诺回答问题！ 输入数据格式： 每个测试包含多个测试用例。第一行包含测试用例数t（1≤t≤10000）。接下来是测试用例的描述。 每个测试用例的第一行包含两个整数n和q（2≤n≤2*10^5，1≤q≤2*10^5）。 每个测试用例的第二行包含n个整数a1，a2，…，an（0≤ai≤10^9）——定义模式的代码部分。 接下来的q行中的第i行包含一个整数vi（0≤vi≤10^9）——乔鲁诺问你一个问题。 所有测试用例的n和q之和不超过2*10^5。 输出数据格式： 打印q个数字。第i个数是乔鲁诺提出的第i个问题的答案。 示例： 输入： 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 3 -1 2 2 4 -1 -1 -1 3 8 1 5 注意： 在第一个测试用例中，a=[2,1,3,3,…]。 - 对于第一个问题，a1=2是索引大于1的最小元素。 - 对于第二个问题，a3=3是索引大于2的最小元素。 - 对于第三个问题，没有索引i使得ai>3。