Magic Number

Problem Description

Illya has $n$ magic numbers. The $i_{th}$ number $a_i$ can be represented by a binary with the length of $i$. Combining these $0-1$ strings gets a long string $s$ with the length of $\frac{n(n+1)}{2}$. The $0-1$ strings from $s_{\frac{i(i-1)}{2}}$ to $s_{\frac{i(i+1)}{2}-1}$ is the binary of $a_i$ from low to high. One day, Rin input Illya’s magic numbers into a program to create $n$ new magic numbers. The $i_{th}$ new number is $b_i$. Here is the code of program in C++: for(int i = 1; i <= n; i++) b[i] = flag[i] = 0; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if( (1 << (j - 1) & a[i]) > 0){ if(!flag[i]) b[i] = b[j], flag[i] = 1; else b[i] &= b[j]; } } b[i] ^= 1 << (i - 1); } After that, Rin leave $q$ questions. The $i_{th}$ question is a number $c_i$, which can be represented by a binary with the length of $len_i$. Combining these $0-1$ strings gets a long string $t$ with the length of $L_q$ ($L_k = \sum_{1}^{k}len_i$). The $0-1$ strings from $t_{L_{i-1}}$ to $t_{L_i-1}$ is the binary of $c_i$ from low to high. For each question, Rin requires Illya to calculate number $d_i$. for(int i = 1; i <= n; i++){ d[i] = 0; for(int j = 1; j <= len[i]; j++) if(j <= n && (1 << (j - 1) & c[i]) > 0) d[i] |= b[j]; } The answer of $i_{th}$ question is the number of ones in the binary of $d_i$.

Input

There are multiple test cases. the first line contains a single integers $T$, denoting the number of test cases. For each case, the first line contains two integers $n$ and $m$, denoting the number of magic numbers and the number of ones in a long string $s$. The second line contains $m$ integers, the $i_{th}$ integer $p1_i$ denotes $s_{p1_i}$ = 1. The others are equal to 0. The third line contains two integer $q$ and $r$, denoting the number of questions and the number of ones in a long string $t$. The forth line contains $q$ integers, the $i_{th}$ integer $len_i$ denotes the length of binary of the $i_{th}$ question $c_i$. The fifth line contains $r$ integers, the $i_{th}$ integer $p2_i$ denotes $t_{p2_i}$ = 1. The others are equal to 0. $1 \leqslant T \leqslant 20$ $1 \leqslant n,q \leqslant 5000$ $1 \leqslant m,r \leqslant 10^6$ $0 \leqslant L_q \leqslant 10^9$ $0 \leqslant p1_i < \frac{n(n+1)}{2}$ $0 \leqslant p2_i < L_q$

Output

For each case, first output "Case #x:". Each question should print one line: the $i_{th}$ line of these denotes the answer of $i_{th}$ question. There is no blank line between two cases.

Sample Input

1
3 4
0 1 4 5
3 6
2 3 3
0 1 2 4 6 7

Sample Output

Case #1:
2
3
3

Author

UESTC

Source

2016 Multi-University Training Contest 6