Election Seat Distribution

There are \(V\) voters and \(N\) parties competing for \(M\) parliamentary seats. Each party \(p\) (numbered from 1 to \(N\)) currently has \(v_p\) votes. In the final count, all parties with less than \(5\%\) of \(V\) votes are disqualified, and no seats are pre‐reserved for any party.

The remaining \(M\) seats are allocated one by one using the following D’Hondt–like procedure: for each party \(p\) (that is not disqualified) with current total votes \(V_p\) and already allocated \(S_p\) seats, compute the quotient

[ Q_p=\frac{V_p}{S_p+1}, ]

and give a seat to the party with the maximum quotient (if there is a tie, the party with the smaller index wins). This process is repeated until all \(M\) seats have been distributed.

However, only a partial count of votes is currently available; that is, we know the current votes \(v_1,v_2,\dots,v_N\) and the remaining votes are \(R = V - \sum_{p=1}^{N} v_p\). Since the remaining votes can be distributed arbitrarily among the parties, determine for each party the minimum and maximum number of seats it can possibly win over all distributions of the remaining votes.

Note: A party is eligible if its final vote total is at least \(0.05\,V\) (i.e. \(5\%\) of \(V\)).

inputFormat

The first line contains three integers: \(V\) (the total number of votes), \(N\) (the number of parties), and \(M\) (the number of seats).

The second line contains \(N\) integers: \(v_1,v_2,\dots,v_N\) representing the current votes each party has obtained.

It is guaranteed that \(\sum_{p=1}^{N} v_p \le V\).

outputFormat

Output \(N\) lines. The \(i\)-th line should contain two integers: the minimum and maximum number of seats that party \(i\) can obtain.

sample

1000 3 5
50 30 20

0 5
0 5
0 5