CF1847F.The Boss's Identity

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 \gt 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 \gt v$. If no such $i$ exists, the answer is $-1$. Help Giorno in answering the questions!

在追踪迪亚波罗的起源时，乔鲁诺从波鲁纳雷夫那里收到了一段秘密代码。该代码可表示为一个无限的正整数序列：$a_1, a_2, \dots $。乔鲁诺立刻看出了这段代码背后的规律。前 $n$ 个数 $a_1, a_2, \dots, a_n$ 已给出；对于 $i > n$，有 $a_i = (a_{i-n}\ |\ a_{i-n+1})$，其中 $|$ 表示按位或运算符。

有关迪亚波罗的信息隐藏在 $q$ 个问题中。每个问题关联一个正整数 $v$，其答案为满足 $a_i > v$ 的最小下标 $i$；若不存在这样的 $i$，则答案为 $-1$。请帮助乔鲁诺回答这些问题！

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

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$）——这是乔鲁诺向你提出的第 $i$ 个问题。

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

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

输出 $q$ 个数。其中第 $i$ 个数是乔鲁诺提出的第 $i$ 个问题的答案。

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 \gt 3$.

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

• 对于第一个询问，$a_1=2$ 是下标大于 $1$ 的元素中下标最小的元素。
• 对于第二个询问，$a_3=3$ 是下标大于 $2$ 的元素中下标最小的元素。
• 对于第三个询问，不存在下标 $i$ 使得 $a_i \gt 3$。