Capitalist Country


Submit solution

Points: 10
Time limit: 6.0s
Memory limit: 512M

Author:
Problem type

Victor lives in a capitalist country where every day, out of the K citizens who have money, the top \left\lfloor\dfrac{K \cdot P}{Q}\right\rfloor of citizens earn one dollar while everyone else loses one dollar. When a citizen runs out of money, he goes bankrupt and loses his citizenship too is no longer one of the K citizens with money. At first, there are N citizens and the i^{th} citizen has a_i dollars. Each citizen has a distinct number of dollars to begin with. Victor would like to know how many days there are until each citizen runs out of money.

Input Specification

The first line contains integers N, P, and Q (1 \leq N, P, Q \leq 10^7, P < Q), the number of citizens in the country and the special numbers P and Q.

The next line will have a list a of N integers, (1 \leq a_i \leq 10^9), the i^{th} of which is how many dollars the i^{th} citizen has. No two citizens have the same amount of money (a_i \neq a_j if i \neq j). The amount of money of the citizens are sorted in increasing order.

Output Specification

In one line, print N integers, the i^{th} of which is how many days there are until the i^{th} citizen runs out of money modulo 10^9+7.

Sample Input 1

5 1 2
1 2 3 4 5

Sample Output 1

1 2 3 8 21

Sample Input 2

2 1 2
999999999 1000000000

Sample Output 2

999999999 999999984

Explanation for Sample 1

At the start, the money count is 1 2 3 4 5.

On day 1, the top \left\lfloor\dfrac{5 \cdot 1}{2}\right\rfloor = 2 citizens gain money, and everyone else loses money. Thus, the new money count becomes 0 1 2 5 6. Here, citizen 1 goes bankrupt on day 1.

The rest of the days are:

0 0 1 6 7 Citizen 2 goes bankrupt on day 2.

0 0 0 5 8 Citizen 3 goes bankrupt on day 3.

0 0 0 4 9

0 0 0 3 10

0 0 0 2 11

0 0 0 1 12

0 0 0 0 13 Citizen 4 goes bankrupt on day 8.

0 0 0 0 12

...

0 0 0 0 1

0 0 0 0 0 The capitalist game finally ends when citizen 5 goes bankrupt on day 21.


Comments

There are no comments at the moment.