Proportional Representation

JAG Kingdom elected the members of its parliament. The country uses only party-list proportional representation: each citizen votes for one party, and the number of seats a party wins is proportional to the number of votes it receives. The parliament has an integer number of seats, so an exactly proportional split is usually impossible. The kingdom splits the seats with the D'Hondt method.

Every party has an unlimited supply of candidates, and the candidates of a party are ordered. The $y$-th candidate of a party that received $x$ votes gets the value $\dfrac{x}{y}$. All candidates are sorted by value in decreasing order, and the first $T$ candidates win, where $T$ is the total number of seats. The number of seats a party wins is the number of its winning candidates.

Take three parties with $40$, $60$ and $30$ votes as an example. With $T = 9$ seats the first party wins $3$ seats, the second wins $4$ seats, and the third wins $2$ seats.

Ties are broken by lottery, so every tied candidate has a chance to win. In the same example with $T = 5$, two candidates tie at the value $20$, and both of the following outcomes are possible.

• The first party wins $2$ seats, the second wins $2$ seats, and the third wins $1$ seat.
• The first party wins $1$ seat, the second wins $3$ seats, and the third wins $1$ seat.

You have just heard the results of the election on TV. You know the total number of valid votes and the number of seats each party won, and you wonder how many votes each party received.

You are given the total number of valid votes $N$, the number of parties $M$, and the number of seats $S_i$ that party $i$ won. For each party, determine the minimum and the maximum number of votes it could have received. For some inputs no vote count produces the given seats at all.

The first line contains two integers $N$ ($1 \le N \le 10^9$) and $M$ ($1 \le M \le 30000$), the total number of valid votes and the number of parties. Each of the next $M$ lines contains one integer $S_i$ ($0 \le S_i \le 30000$), the number of seats party $i$ won. At least one $S_i$ is not zero.

If no vote count produces the given $N$, $M$ and $S_i$, print impossible. Otherwise print $M$ lines. The $i$-th line contains two integers, the minimum and the maximum number of votes party $i$ could have received.