Proportional Representation

Today is election day for members of the National Assembly.

A total of V people voted, and each voter chose one of N parties. Exactly M seats will be assigned.

Seats are assigned by the D'Hondt method with a 5% threshold. The parties are numbered from 1 to N, and their final vote counts are V_1, V_2, ..., V_N. The assignment works as follows.

1. A party that receives fewer than 5% of the total votes V is removed from seat allocation.
2. Initially, every party has 0 seats.
3. For each remaining party P, compute Q_P = V_P / (S_P + 1), where S_P is the number of seats already assigned to party P.
4. The party with the largest Q_P receives one seat. If several parties are tied, the party with the smallest number receives the seat.
5. Repeat steps 3 and 4 until all seats have been assigned.

The vote count is still in progress. You know how many votes each party has received so far, but the destinations of the uncounted votes are unknown.

Given the current partial results, compute the maximum and minimum number of seats each party can end up with.

The first line contains the total number of votes V, the number of parties N, and the number of seats M. (1 <= V <= 10,000,000, 1 <= N <= 100, 1 <= M <= 200)

The second line contains the number of votes currently received by each party, in party-number order. Their sum does not exceed V.

On the first line, print the maximum possible number of seats for each party in party-number order.

On the second line, print the minimum possible number of seats for each party in party-number order.

In the first sample test, 14 votes have been counted and 6 votes remain. Suppose the remaining votes add 2, 0, 1, 3 votes to parties 1 through 4. The final vote counts become 6, 3, 7, 4, so every party passes the threshold.

The seats are then assigned to parties 3, 1, 4, 3, and 1, giving final seat counts 2, 0, 2, 1. Therefore, it is possible for party 2 to receive no seats.