Defeat the Boss

You are challenged by a big boss who has a quantifiable confidence level \(C\) (a positive integer). The only way to defeat the boss is to reduce his confidence to exactly 0 (not below 0, since negative confidence would trigger his evolution and you would be instantly defeated).

You, as an OI contestant, have your own attributes. Your self‐confidence is also quantified and you have an upper limit \(mc\). Initially (day 1, before any attack) your self‐confidence is \(mc\), your level \(L\) is 0, and your sarcasm ability \(F\) is 1.

The contest lasts for \(n\) days. In each day \(i\) (for \(i \ge 1\)) the following events occur in order:

1. The boss launches a taunt which decreases your self‐confidence by \(a_i\). If your self‐confidence becomes < 0 after this attack, you lose immediately. (Note that if it becomes exactly 0 you can still continue fighting.)
2. If you survive the attack (i.e. your self‐confidence is \(\ge 0\)), you must and can only choose one of the following actions:

• Retort: The boss is momentarily surprised and his confidence decreases by 1. (This action can only be performed if the boss’s current confidence is at least 1.)
• Do an Easy Problem: Your self‐confidence increases by \(w_i\), but if it exceeds \(mc\) after the increase then it is set to \(mc\).
• Level Up: Your level \(L\) increases by 1.
• Boost Sarcasm: Your sarcasm ability \(F\) is multiplied by your current level \(L\) (i.e. updated to \(F \cdot L\)).
• Criticize the Boss: You decrease the boss’s confidence by \(F\) (this operation is only allowed if the boss’s current confidence is at least \(F\)). After this action, your level resets to 0 and your sarcasm ability resets to 1. This action is limited to at most two uses during the entire contest.

Important: At any moment you must never cause the boss’s confidence to become negative. The actions affecting the boss’s confidence (Retort and Criticize the Boss) must be applied only if the current boss confidence is at least the amount you are about to subtract.

You will face one boss in a contest. However, you have learned that there are m bosses in the world, each possessing the same taunt schedule \(a_1, a_2, \dots, a_n\) (and similarly, the recovery amounts \(w_1, w_2, \dots, w_n\) if you do an easy problem). For your preparation you need to determine, for each boss with a given initial confidence \(C\), whether you can choose a sequence of actions over the \(n\) days so that the boss’s confidence becomes exactly 0 by the end. If you fail to achieve exactly 0, you lose because on day \(n+1\) the boss will decisively defeat you.

Input and output on each boss are considered separately (that is, in a contest you fight only one boss, and the actions you take do not affect fights with other bosses).

Note: All formulas must be represented in LaTeX (for example, using \(\) or \[ \] constructs).

inputFormat

Input Format:

 m n mc
 a1 a2 ... an
 w1 w2 ... wn
 C1 C2 ... Cm

Where:

• m is the number of bosses.
• n is the number of days.
• mc is your self‐confidence upper limit.
• ai is the self‐confidence reduction (due to the boss’s taunt) on day \(i\).
• wi is the amount your self‐confidence is increased if you do an easy problem on day \(i\).
• Cj is the initial confidence of the j-th boss.

outputFormat

Output Format:

For each boss, output a single line containing either "Yes" if you can reduce his confidence exactly to 0 using a valid sequence of actions over the \(n\) days, or "No" if it is impossible.

sample

2 3 10
2 3 4
5 0 5
2 5

Yes
No

</p>