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.

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

Case #1:
2
3
3

Author

UESTC