L. Equalize
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of $$$n$$$ non-negative integers, and a positive integer $$$m$$$.

You need to answer $$$q$$$ queries. In each query, you are given a non-negative integer $$$x$$$.

You can do the following operation:

  • choose two integers $$${1 \le l \le r \le n}$$$ such that $$${r - l + 1 = m}$$$, and for each $$${l \le i \le r}$$$ replace $$$a_i$$$ with $$${a_i \space | \space x}$$$. where $$${x \space | \space y}$$$ denotes the bit-wise OR of $$$x$$$ and $$$y$$$.
You need to make all the elements of the array equal.

For each query, output the minimum number of operations needed to make the elements of the array equal, or output $$$-1$$$ if they cannot be made equal.

Input

The first line contains a single positive integer $$${1 \le t \le 3 \times 10^5}$$$ — the number of testcases.

The first line of each testcase contains two positive integers $$$n$$$ and $$$m$$$ $$${(1 \le m \le n \le 10^6)}$$$.

The next line contains $$$n$$$ non-negative integers $$${a_1, \space a_2, \space ..a_n}$$$ — the elements of array $$$a$$$, where $$$({0 \le a_i \lt 2^{30}})$$$.

The next line contains a single positive integer $$$q$$$ $$${(1 \le q \le 10^6)}$$$ — the number of queries.

Each of the following $$$q$$$ lines contains a single non-negative integer $$$({0 \le x \lt 2^{30}})$$$.

It is guaranteed that the sum of $$$n$$$ and $$$q$$$ over all testcases does not exceed $$${10^6}$$$.

Output

For each query of each testcase, output the answer to it as described in the problem statement.

Example
Input
2
2 1
1 3
2
2
4
6 2
22 4 14 30 28 12
4
26
27
30
31
Output
1
-1
3
3
3
3