Rikka with Candies
time limit per test 3.5 second memory limit per test 256 megabytes
As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

There are n children and m kinds of candies. The ith child has Ai dollars and the unit price of the ith kind of candy is Bi. The amount of each kind is infinity.

Each child has his favorite candy, so he will buy this kind of candies as much as possible and will not buy any candies of other kinds. For example, if this child has 10 dollars and the unit price of his favorite candy is 4 dollars, then he will buy two candies and go home with 2 dollars left.

Now Yuta has q queries, each of them gives a number k. For each query, Yuta wants to know the number of the pairs (i,j)(1≤i≤n,1≤j≤m) which satisfies if the ith child’s favorite candy is the jth kind, he will take k dollars home.

To reduce the difficulty, Rikka just need to calculate the answer modulo 2.

But It is still too difficult for Rikka. Can you help her?

传送门:HDU6085

Input

The first line contains a number t(1≤t≤5), the number of the testcases. For each testcase, the first line contains three numbers n,m,q(1≤n,m,q≤50000). The second line contains n numbers Ai(1≤Ai≤50000) and the third line contains m numbers Bi(1≤Bi≤50000). Then the fourth line contains q numbers ki(0≤ki<maxBi) , which describes the queries. It is guaranteed that Ai≠Aj,Bi≠Bj for all i≠j.

Output

For each query, print a single line with a single 01 digit -- the answer.

Sample Input

1
2
3
4
5
1
5 5 5
1 2 3 4 5
1 2 3 4 5
0 1 2 3 4

Sample Output

1
2
3
4
5
0
0
0
0
1

题解

学到了BitSet能够优化集合的交并计算 a%b=k -> (a-k)%b==0 然后枚举k要从大到小(这样加b的倍数才不会出错 因为k总是小于b的) 还有因为%2就可以转换成01的表示 http://blog.csdn.net/mengxiang000000/article/details/76927147 建议参考这篇博客
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import java.io.*;  
import java.util.*;
public class Main {

public static void main(String[] args) {
FastScanner sc=new FastScanner();
PrintWriter pw=new PrintWriter(System.out);
int t=sc.nextInt();
BitSet bit=new BitSet(50050);
BitSet ans=new BitSet(50050);
while(sc.hasNext()){
bit.clear();
ans.clear();
int n=sc.nextInt();
int m=sc.nextInt();
int q=sc.nextInt();
int[]a=new int[n];
int[]b=new int[m];
int[]sum=new int[50050];
int[]res=new int[50050];
boolean[]vis=new boolean[50050];
for(int i=0;i<n;i++){
a[i]=sc.nextInt();
bit.set(a[i]);
}
int max=-1;
for(int i=0;i<m;i++){
b[i]=sc.nextInt();
vis[b[i]]=true;
max=Math.max(b[i], max);
}
for(int i=max;i>=0;i--){
BitSet temp=bit.get(i, 50050);
temp.and(ans);
res[i]=temp.cardinality()%2;
if(vis[i]){
for(int j=0;j<=max;j+=i){ //加入b的倍数 满足后续i都比加入的这个b小
ans.flip(j);
}
}
}
for(int i=0;i<q;i++){
int index=sc.nextInt();
pw.println(res[index]);
}
pw.flush();
}

}
}