题目描述

$JAG$ 王国举行了议会议员选举。这个国家唯一采用的制度是政党名单比例代表制。在这个系统中，每个公民投票给一个政党，一个政党赢得的席位数量将与其获得的选票数量成正比。由于议会席位总数是整数，当然，通常不可能完全按比例分配席位。在 $JAG$ 王国中，使用以下称为 $D'Hondt$ 方法的方法来确定每一方的席位数量。

假设每一方都有无限的候选人供应，并且每一方的候选人都以某种方式排序。对于获得 $x$ 票的政党的第 $y$ 候选人，分配价值 $\dfrac{x}{y}$。然后所有候选者按其分配价值的降序排序。第一个 $T$ 候选人被认为获胜，其中 $T$ 是席位总数，一个政党赢得的席位数是其获胜候选人的数量。

下面显示了一个包含三方的示例。

第一个政党获得了 $40$ 票的选票，第二个获得了 $60$ 票的选票，第三个获得了 $30$ 票的选票。如果席位总数为 $T = 9$ ，则第一方将赢得 $3$ 个席位，第二方 $4$ 个席位，第三方 $2$ 个席位。

在选择获胜候选人时：

• 以抽签方式打破平局；
• 任何并列的候选人都有机会获胜。

例如，在上面的示例中，如果 $T = 5$，那么两个候选人的价值为 $20$，并且有两种可能的结果：

1. 第一方赢得 $2$ 个席位、第二方 $2$ 个席位，第三方 $1$ 个席位。

2. 第一方赢得 $1$ 个席位、第二方 $3$ 个席位，第三方 $1$ 个席位。

你刚刚在电视上听到了选举结果。知道有效票的总数和每一方赢得的席位数，你想知道每一方获得了多少票。

给定 $N$ , $M$ 和 $S_i$ $\begin{pmatrix}1 \le i \le M\end{pmatrix}$，分别表示有效票总数，政党数量和第 $i$ 政党赢得的席位数量，你的任务是分别为每一方确定它收到的最小和最大可能的票数。请注意，在某些情况下，给定的 $N$ ，$M$ 和 $S_i$ 可能不存在这种情况。

输入格式

输入的第一行包含两个整数 $N$ $\begin{pmatrix}1 \le N \le 10^9 \end{pmatrix}$ 和 $M$ $\begin{pmatrix}1 \le M \le 30{,}000 \end{pmatrix}$ ，其中 $N$ 是有效票数的总数 ，$M$ 是参与方的数量。

接下来是 $M$ 行，其中第 $i$ 行包含一个整数 $S_i$ $\begin{pmatrix}0 \le S_i \le 30{,}000 \end{pmatrix}$，代表第 $i$ 党赢得的席位数。你可以假设存在 $i$ 且 $S_i \ne 0$。

输出格式

如果给定的 $N$ ， $M$ 和 $S_i$ 不存在任何情况，则显示 impossible一词。否则，输出 $M$ 行，每行包含两个整数。第 $i$ 行中的第一个整数和第二个整数应该分别是第 $i$ 方获得的最小和最大可能票数。 $\\$

$\textrm{\textit{\textbf{Sample Input 1}}}$ :$\\$ $10\;2\\$ $2\\$ $1\\$ $\textrm{\textit{\textbf{Output for the Sample Input 1}}}$ :$\\$ $5\;7\\$ $3\;5\\$

$\textrm{\textit{\textbf{Sample Input 2}}}$ : $\\$ $5\;6\\$ $0\\$ $2\\$ $0\\$ $2\\$ $6\\$ $0\\$ $\textrm{\textit{\textbf{Output for the Sample Input 2}}}$ :$\\$ $0\;0\\$ $1\;1\\$ $0\;0\\$ $1\;1\\$ $3\;3\\$ $0\;0\\$