Pusheen is playing Neko Atsume! She has a lot of toys and has laid them out to maximize her fish income. She wants to know how efficient her layout will be though.

After doing a lot of critical thinking and real-time programming, Pusheen has boiled down the fish income in terms of a single variable - the beauty of the arrangement of toys. She thus defines $f(x)$ to be the fish income given that her layout has beauty $x$. After some more computation, Pusheen has realized that for all $x\le 0$, $f(x)=1$. Otherwise, $f(x)=f\left(\lfloor \frac{x}{a}-b\rfloor \right)+f\left(\lfloor \frac{x}{c}-d\rfloor \right)$.

Pusheen has $Q$ layouts, layout $i$ having beauty $x_i$. Compute $f(x_i)$ for many values of $x_i$.

Constraints

$1\le x_i\le {10}^9$

$2\le a,c\le {10}^9$

$0\le b,d\le {10}^9$

$1\le Q\le {10}^5$

Input Specification

The first line contains five space-separated integers, $a$, $b$, $c$, $d$, and $Q$.

The next $Q$ lines each contain a single positive integer, $x_i$.

Output Specification

Output $Q$ lines, the $f(x_i)$ values in order.

Sample Input

2 0 2 0 3
1
2
3

Sample Output

2
4
4