Problem C: Election of Representatives

The D’Hondt method is frequently used for allocation of parliamentary seats to parties, in proportion to the number of their received votes, balanced with minority representation. The representatives allocation algorithm is based on successive calculation, for each party, of quotients

where v_i is the total number of votes in party i and s_i is the number of seats or representatives already allocated to that same party.

To begin, we calculate the quotients for each party with s = 0. At the end of each round we assign a seat to the party (k) with the highest quotient, so s_k is increased by 1. The first representatives place goes always to the most voted party. In the second iteration, s is 0 for all but the most voted, which means that its quotient value will be lower than before. Again, the party having the highest quotient in this round gets the next representative seat.

In case of a tie in the highest quotient value, on some round, the place is assigned to the least voted party in dispute. In this case, if there is still a tie in the number of votes of various parties, the seat is allocated to the party with the lowest index. The process ends when all seats are assigned.

Task

Implement a program to distribute parliamentary seats to parties, according to the election results and using the D’Hondt method as explained above.

Input

The first line has the total number of seats (S) for parliamentary representatives to be distributed. The second line has the number of parties (P). The following P lines, one for each party, have the number of votes (V) for that party. The party index, mentioned above, is an implicit integer starting from 1, with successive values from line to line.

Constraints

Output

The program’s output is made up of as many lines as there are parties. For each party, and arranged in identical order as in input, your program should write a line with the number of seats that were assigned to it.

Sample Input

3
4
20
12
8
2

Sample Output

2
1
0
0

Sample Explanation

To better understand this example, we can see the intermediate computations of each round in Table 1.

Party 1 has the highest quotient (in bold), so it receives the first representative seat. Quotients for rounds 2 and 3 are shown in the next lines. In round 2 the seat goes to party 2. And in the last round, the highest quotient appears again in party 1, resulting in its second seat.

After round 3 there are no more seats to assign, so the process ends with the output presented before, meaning that 2 seats were given to party 1, 1 seat to party 2, and zero to the remaining parties.