Rikka with Candies

Problem Description

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 $i$th child has $A_i$ dollars and the unit price of the $i$th kind of candy is $B_i$. 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 \leq i \leq n,1 \leq j \leq m)$ which satisfies if the $i$th child¡¯s favorite candy is the $j$th 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?

Input

The first line contains a number $t(1 \leq t \leq 5)$, the number of the testcases. For each testcase, the first line contains three numbers $n,m,q(1 \leq n,m,q \leq 50000)$. The second line contains $n$ numbers $A_i(1 \leq A_i \leq 50000)$ and the third line contains $m$ numbers $B_i(1 \leq B_i \leq 50000)$. Then the fourth line contains $q$ numbers $k_i(0 \leq k_i < \max B_i)$ , which describes the queries. It is guaranteed that $A_i \neq A_j, B_i \neq B_j$ for all $i \neq j$.

Output

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

Sample Input

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

Sample Output

0
0
0
0
1

Source

2017 Multi-University Training Contest - Team 5

https://acm.hdu.edu.cn/showproblem.php?pid=6085