Limits 2s, 512 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 QQ locks each of which is some integer xix_i. You have an array of NN integers: a1a_1, a2a_2, a3a_3, …, ana_n. A key for a lock xix_i is some non-empty subset of any positive size kk containing s1s_1, s2s_2, …, sks_k of the array such that xi&(s1s2...sk)==0x_i \mathbin{\&} (s_1 \mathbin{|} s_2 \mathbin{|} ... \mathbin{|} s_k) == 0, where &\mathbin{\&} means bitwiseANDbitwise\hspace{1mm}AND and \mathbin{|} means bitwiseORbitwise\hspace{1mm}OR. But, as you are a problem solver, you wonder how many subsets of your array exist as keys for a lock xix_i.

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

Input

Input starts with an integer TT (1T51 ≤ T ≤ 5), denoting the number of test cases. Each case contains two integers NN (1N1051 ≤ N ≤ 10^5) and QQ (1Q1051 ≤ Q ≤ 10^5), denoting the number of elements of the array and the number of locks.

The next line contains NN integers a1a_1, a2a_2, …, ana_n (1ai1061 ≤ a_i ≤ 10^6).

Each of the following QQ lines contains an integer xix_i (1xi1061 ≤ x_i ≤ 10^6), denoting a lock of the maze.

Output

For each test case, print "Case T:" (without quote) in the first line, where TT is the case number. Each of the next QQ lines should contain a single integer yiy_i, denoting the number of valid keys exist in the array modulo 1000000007 for the lock xix_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

Submit

Login to submit.

Contributors

Statistics

77% Solution Ratio
nfs277Earliest, Jun '20
mbsabbirr127Fastest, 0.1s
mbsabbirr127Lightest, 5.7 MB
Tahmid690Shortest, 687B
Toph uses cookies. By continuing you agree to our Cookie Policy.