사탕

Rikka는 수학을 잘 못한다. Yuta는 그것이 걱정되어 Rikka에게 수학 연습 문제를 준다. 그중 하나는 다음과 같다.

$n$명의 어린이와 $m$종류의 사탕이 있다. $i$번째 어린이는 $A\_i$달러를 가지고 있고, $i$번째 종류의 사탕의 개당 가격은 $B\_i$달러이다. 각 종류의 사탕은 무한히 공급된다.

각 어린이는 가장 좋아하는 사탕이 있어서, 그 종류의 사탕만 가능한 한 많이 살 것이고 다른 종류의 사탕은 사지 않는다. 예를 들어, 어린이가 $10$달러를 가지고 있고 가장 좋아하는 사탕의 개당 가격이 $4$달러라면, 사탕을 두 개 사고 $2$달러를 남긴 채 집에 간다.

Yuta는 어떤 어린이의 가장 좋아하는 사탕도 모른다. Yuta에게는 $q$개의 질의가 있고, 각 질의는 정수 $k$ 하나로 이루어진다. 각 질의에 대해 Yuta는 다음 성질을 만족하는 쌍 $(i, j)$ ($1 \leq i \leq n$, $1 \leq j \leq m$)의 개수를 알고 싶어한다: $i$번째 어린이가 가장 좋아하는 사탕이 $j$번째 종류라면, 그 어린이는 $k$달러를 가지고 집에 간다.

문제를 쉽게 하기 위해 답을 $2$로 나눈 나머지만 계산하면 된다. Yuta를 위해 Rikka가 이 문제를 풀도록 도와주자!

첫째 줄에 세 정수 $n$, $m$, $q$가 주어진다 ($1 \leq n, m, q \leq 5 \cdot 10^4$).

둘째 줄에 $n$개의 정수 $A\_i$가 주어진다 ($1 \leq A\_i \leq 5 \cdot 10^4$).

셋째 줄에 $m$개의 정수 $B\_i$가 주어진다 ($1 \leq B\_i \leq 5 \cdot 10^4$).

넷째 줄에 질의를 나타내는 $q$개의 정수 $k\_i$가 주어진다 ($0 \leq k\_i < \max (B\_1, B\_2, \ldots, B\_m)$).

$i \neq j$인 모든 $i, j$에 대해 $A\_i \neq A\_j$이고 $B\_i \neq B\_j$임이 보장된다.

각 질의에 대해 답을 $2$로 나눈 나머지를 한 줄에 하나씩 출력한다.