Description

People inevitably run into “dalao.” They swagger around, talking about algorithms and data structures that ordinary folks cannot grasp. Wherever they go, their presence makes others tremble and fall silent. As an OIer, you are very unhappy about this and make some disrespectful remarks. The dalao starts to take revenge on you, and you refuse to back down, vowing to bring them down. Let us explain what a dalao is: besides being a “shen niu,” a dalao also has strong self-confidence, which can be quantified by a positive integer $C$. The only way to defeat a dalao is to destroy their self-confidence, i.e., make the dalao’s confidence value equal to $0$ (exactly $0$, not less than $0$). Since you are targeted, you must prepare for $n$ days to contend with the dalao: during these $n$ days the dalao will only mock you to shake your confidence. On day $n+1$, if the dalao finds you still unconvinced, they will crush you directly, and you will lose the ability to fight.

Your confidence can also be quantified. Let $\mathrm{mc}$ be your confidence upper bound. On day $i$ ($i \ge 1$), the dalao taunts you once, decreasing your confidence by $a_i$. If at that moment your confidence becomes less than $0$, you lose the ability to fight and thus fail (note in particular that when your confidence is $0$, you can still continue to fight the dalao). On that day, after the dalao’s taunt, if your confidence is still at least $0$, you can and only can choose exactly one of the following actions:

1. Talk back once. The dalao is a bit surprised, so the dalao’s confidence $C$ decreases by $1$.
2. Solve easy problems for a day, increasing your current confidence by $w_i$, then compare the new confidence with the upper bound $\mathrm{mc}$. If the new confidence exceeds $\mathrm{mc}$, set it to $\mathrm{mc}$. For example, if $\mathrm{mc} = 50$, your current confidence is $40$, and $w_i = 5$, then the new confidence is $45$; if $w_i = 11$, then the new confidence is $50$.
3. Increase your level $L$ by $1$.
4. Multiply your taunt power $F$ by your current level $L$, i.e., update $F$ to $F \cdot L$.
5. Roast the dalao, decreasing the dalao’s confidence $C$ by $F$. After roasting the dalao, your level $L$ automatically drops to $0$, and your taunt power $F$ becomes $1$. Since roasting the dalao costs reputation, this operation can be performed at most twice.

Pay special attention: at any time, you must not make the dalao’s confidence negative. A negative confidence value is a humiliation to the dalao, and whenever humiliated, the dalao evolves into an even stronger dalao who instantly crushes you. On day $1$, before you are attacked, your confidence is full (initial confidence equals the upper bound $\mathrm{mc}$), your taunt power $F$ is $1$, and your level $L$ is $0$.

Since you have offended the dalao, you must prepare to confront them head-on. You know there are $m$ dalao in the world. Their taunting lasts $n$ days, and the taunt value on day $i$ is $a_i$. No matter which dalao you face, the confidence recovery from solving easy problems on day $i$ is $w_i$. Among these $m$ dalao, exactly one will fight you (the same one for all $n$ days). But you need to know, for each dalao, whether you can destroy their confidence, i.e., make their confidence value exactly $0$. When you fight one dalao, the others do not interfere.

Input Format

The first line contains three positive integers $n, m, \mathrm{mc}$, denoting that there are $n$ days and $m$ dalao, and your confidence upper bound is $\mathrm{mc}$.

The next line contains $n$ integers separated by spaces. The $i$-th ($1 \le i \le n$) denotes $a_i$.

The next line contains $n$ integers separated by spaces. The $i$-th ($1 \le i \le n$) denotes $w_i$.

Then follow $m$ lines, each containing one positive integer. On the $k$-th ($1 \le k \le m$) line, the integer $C_k$ denotes the initial confidence of the $k$-th dalao.

Output Format

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

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

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

Hint

• For $20\%$ of the testdata, $1 \le n \le 10$.
• For another $20\%$ of the testdata, $1 \le C_i, n, \mathrm{mc} \le 30$.
• For $100\%$ of the testdata, $1 \le n, \mathrm{mc} \le 100$, $1 \le m \le 20$, $1 \le a_i, w_i \le \mathrm{mc}$, $1 \le C_i \le 10^8$.

Translated by ChatGPT 5