Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Osim's Maze

By Muhimin_Osim · Limits 2s, 256 MB

Welcome to Osim’s maze!

Unfortunately, you are in the maze right now and you want to come outside the maze. But, in order to do that, you have to unlock some locks with keys. So, you are given $Q$ locks each of which is some integer $x_i$. You have an array of $N$ integers: $a_1, a_2, a_3, \dots, a_n$. A key for a lock $x_i$ is some non-empty subset of any positive size $k$ containing $s_1, s_2, \dots, s_k$ of the array such that $x_i \mathbin{\&} (s_1 \mathbin{|} s_2 \mathbin{|} ... \mathbin{|} s_k) == 0$ , where $\mathbin{\&}$ means $bitwise\hspace{1mm}AND$ and $\mathbin{|}$ means $bitwise\hspace{1mm}OR$. But, as you are a problem solver, you wonder how many subsets of your array exist as keys for a lock $x_i$.

Since the answer can be too large, you have to find the number $modulo$ $1000000007$.

Input

Input starts with an integer $T$, denoting the number of test cases.
Each case contains two integers $N$ and $Q$, denoting the number of elements of the array and the number of locks.
The next line contains $N$ integers $a_1, a_2, \dots, a_n$.
Each of the following $Q$ lines contains an integer $x_i$, denoting a lock of the maze.

Constraints

$1 ≤ T ≤ 5$
$1 ≤ N ≤ 10^5$
$1 ≤ Q ≤ 10^5$
$1 ≤ a_i ≤ 10^6$
$1 ≤ x_i ≤ 10^6$

Subtask 1 (10 points)

$1 ≤ T ≤ 5$
$1 ≤ N ≤ 15$
$1 ≤ Q ≤ 10^5$
$1 ≤ a_i ≤ 10^6$
$1 ≤ x_i ≤ 10^6$

Subtask 2 (30 points)

$1 ≤ T ≤ 5$
$1 ≤ N ≤ 10^4$
$1 ≤ Q ≤ 10^5$
$1 ≤ a_i ≤ 10^3$
$1 ≤ x_i ≤ 10^3$

Subtask 3 (60 points)

Original constraints

Output

For each test case, print “Case T:” (without quote) in the first line, where $T$ is the case number. Each of the next $Q$ lines should contain a single integer $y_i$, denoting the number of valid keys exist in the array $modulo$ $1000000007$ for the lock $x_i$.

Sample

InputOutput
2
4 1
1 2 3 4
4
4 2
2 2 3 5
5
2
Case 1:
7
Case 2:
3
1

    Discussion

    Statistics


    43% Solution Ratio

    nfs277Earliest, 1M ago

    chayankumar999Fastest, 0.2s

    YouKnowWhoLightest, 9.3 MB

    YouKnowWhoShortest, 938B

    Submit

    Login to submit