Problem Description

There are $V$ voters voting in an election. In this election, $N$ parties participate and compete for $M$ seats in the parliament.

Assume the parties are numbered from $1$ to $N$, and they receive $v_1, v_2, \cdots, v_n$ votes respectively. Seats are allocated as follows:

1. Any party that gets less than $5\%$ of the votes is directly disqualified from further seat allocation.

2. At the beginning, no seats are reserved for any party.

3. For each party, compute $Q_p = V_p \div (S_p + 1)$, where $V_p$ is the total votes received by the party, and $S_p$ is the number of seats already allocated to that party.

4. The party with the largest $Q_p$ gets one seat. (If tied, the party with the smaller index gets it.)

5. Repeat steps 3 and 4 until all seats are allocated.

Now some ballots have been counted, and the current vote counts of the parties are known. Write a program to determine, over all possible situations, the maximum or minimum number of seats each party can obtain.

Input Format

The first line contains three positive integers $V, N, M$.

The second line contains $N$ positive integers, the current vote counts of each party. It is guaranteed that their sum does not exceed $V$.

Output Format

Output $N$ integers on the first line, the maximum possible number of seats each party can obtain.

Output $N$ integers on the second line, the minimum possible number of seats each party can obtain.

20 4 5
4 3 6 1

3 3 3 2
1 0 1 0

100 3 5
30 20 10

4 3 3
1 1 0

Hint

Correctly outputting the first line earns $20\%$ of the score. Correctly outputting the second line earns $80\%$ of the score.

Constraints: $1 \le V \le 10^7$, $1 \le N \le 100$, $1 \le M \le 200$.

Translated by ChatGPT 5