People often encounter "big shots" (dalao). They talk arrogantly about algorithms and data structures that mortals cannot understand. Wherever they go, their aura makes those around them tremble in fear, unable to speak. As an OIER, you are very unhappy with this situation, so you make disrespectful remarks about them. The big shot begins to retaliate, and you, not to be outdone, threaten to defeat them.

Now, let me explain what a big shot is. Besides being a genius, a big shot has strong self-confidence, which can be quantified as a positive integer $C$ ($1 \le C \le 10^8$). The only way to defeat a big shot is to destroy their self-confidence, which means making their confidence value equal to $0$ (exactly $0$, not less than $0$). Since you have been targeted by a big shot, you need to prepare for $n$ ($1 \le n \le 100$) days of confrontation, because during these $n$ days, the big shot will only mock you to shake your confidence. On the $(n+1)$-th day, if the big shot finds that you are still not submissive, they will directly crush you until you are, causing you to lose the ability to fight.

Your confidence level can also be quantified. We use $mc$ ($1 \le mc \le 100$) to represent your maximum confidence value. On day $i$ ($i \ge 1$), the big shot will launch a mockery at you, causing your confidence value to decrease by $a[i]$. If your confidence value becomes less than $0$ at this moment, you lose the ability to fight and fail (note specifically that you can continue to fight the big shot when your confidence value is $0$). On this day, after the big shot launches the mockery, if your confidence value is still greater than or equal to $0$, you can and must choose one of the following actions:

1. Talk back: The big shot will be slightly surprised, causing their confidence value $C$ to decrease by $1$.
2. Solve a "water" (easy) problem for the day: Your current confidence value increases by $w[i]$. Compare the new confidence value with the maximum confidence value $mc$. If the new value is greater than $mc$, it is updated to $mc$. For example, if $mc=50$, current confidence is $40$, and $w[i]=5$, the new confidence is $45$. If $w[i]=11$, the new confidence is $50$.
3. Increase your level $L$ by $1$.
4. Multiply your sarcasm ability $F$ by your current level $L$, updating $F$ to $F \times L$.
5. Confront the big shot: The big shot's confidence value $C$ decreases by $F$. After confronting the big shot, your level $L$ automatically drops to $0$, and your sarcasm ability $F$ drops to $1$. Since confronting the big shot is detrimental to your reputation, this operation can be performed at most $2$ times.

Special note: At any time, you cannot let the big shot's confidence value be negative, because for a big shot, a negative confidence value means humiliation, and whenever a big shot encounters humiliation, they will evolve into a more powerful big shot and crush you. On day $1$, before you are attacked, your confidence is full (initial confidence equals the maximum confidence $mc$), your sarcasm ability $F$ is $1$, and your level $L$ is $0$.

Now, because you have offended the big shots, you need to prepare to face them head-on. You know there are $m$ ($1 \le m \le 20$) big shots in the world. Their mockery duration is $n$ days, and the mockery value on day $i$ is $a[i]$. Regardless of which big shot you compete with, your confidence recovery from solving a water problem on day $i$ is $w[i]$. Only one of these $m$ big shots will come to compete with you (this big shot will compete with you for all $n$ days). However, you need to know for any given big shot whether you can destroy their confidence, i.e., make their confidence value exactly $0$. When competing with one big shot, other big shots will not interfere.

Input

The first line contains three positive integers $n, m, mc$. They represent the number of days, the number of big shots, and your maximum confidence value, respectively.

The next line contains $n$ space-separated integers, where the $i$-th ($1 \le i \le n$) integer represents $a[i]$.

The next line contains $n$ space-separated integers, where the $i$-th ($1 \le i \le n$) integer represents $w[i]$.

The next $m$ lines each contain a positive integer, where the $k$-th ($1 \le k \le m$) line contains the integer $C[k]$, representing the initial confidence value of the $k$-th big shot.

Output

Output $m$ lines. If you can defeat the $k$-th big shot (making their confidence value exactly $0$), output $1$ on the $k$-th line; otherwise, output $0$.

Examples

Input 1

30 20 30
15 5 24 14 13 4 14 21 3 16 7 4 7 8 13 19 16 5 6 13 21 12 7 9 4 15 20 4 13 12
22 21 15 16 17 1 21 19 11 8 3 28 7 10 19 3 27 17 28 3 26 4 22 28 15 5 26 9 5 26
30
10
18
29
18
29
3
12
28
11
28
6
1
6
27
27
18
11
26
1

Output 1

0
1
1
0
1
0
1
1
0
0
0
1
1
1
1
1
1
0
0
1

Constraints

$20\%$ of the data: $1 \le n \le 10$.

Another $20\%$ of the data: $1 \le C[i], n, mc \le 30$.

$100\%$ of the data: $1 \le n, mc \le 100$; $1 \le m \le 20$; $1 \le a[i], w[i] \le mc$; $1 \le C[i] \le 10^8$.