Mock CCC '19 Contest 1 S4 - Pusheen Plays Neko Atsume

View as PDF

Submit solution


Points: 12
Time limit: 1.0s
Java 2.0s
Memory limit: 1G

Problem type

NOTE: The test data for this problem are stronger than the contest version. Solutions that AC there may not get AC here.

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(\left \lfloor \frac{x}{a} - b \right\rfloor \right) + f\left(\left\lfloor \frac{x}{c} - d \right\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

Comments

There are no comments at the moment.