Rikka 不擅长数学。Yuta 很担心这一点，于是他给 Rikka 出了一些数学题来练习。其中一道题描述如下。

有 $n$ 个孩子和 $m$ 种糖果。第 $i$ 个孩子有 $A_i$ 美元，第 $j$ 种糖果的单价为 $B_j$。每种糖果都有无限的供应量。

每个孩子都有她最喜欢的糖果，所以她会尽可能多地购买这种糖果，而不会购买其他种类的糖果。例如，如果一个孩子有 10 美元，她最喜欢的糖果单价为 4 美元，那么她会买两块糖果，并带着 2 美元回家。

Yuta 不知道任何孩子最喜欢的糖果。现在 Yuta 有 $q$ 次询问，每次询问包含一个整数 $k$。对于每次询问，Yuta 想知道满足以下条件的数对 $(i, j)$ ($1 \le i \le n, 1 \le j \le m$) 的数量：如果第 $i$ 个孩子最喜欢的糖果是第 $j$ 种，她回家时会剩下 $k$ 美元。

为了简化问题，只需要计算答案模 2 的结果。请帮 Rikka 解决这个问题！

输入格式

第一行包含三个整数 $n, m$ 和 $q$ ($1 \le n, m, q \le 5 \cdot 10^4$)。

第二行包含 $n$ 个整数 $A_i$ ($1 \le A_i \le 5 \cdot 10^4$)。

第三行包含 $m$ 个整数 $B_j$ ($1 \le B_j \le 5 \cdot 10^4$)。

第四行包含 $q$ 个整数 $k_i$，描述了询问 ($0 \le k_i < \max(B_1, B_2, \dots, B_m)$)。

保证对于所有 $i \neq j$，都有 $A_i \neq A_j$ 且 $B_i \neq B_j$。

输出格式

对于每次询问，输出一行，包含一个整数：答案模 2 的结果。

样例

样例输入 1

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

样例输出 1

0
0
0
0
1