codeforces#P1847F. The Boss's Identity
The Boss's Identity
Description
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!
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$.
Print $q$ numbers. The $i$-th number is the answer to the $i$-th question asked by Giorno.
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.
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
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$.