问题陈述
JAG王国举行了议会议员选举。 该国采用的唯一制度是政党名单比例代表制。 在这个系统中,每个公民投票给一个政党,一个政党赢得的席位数量将与其获得的选票数量成正比。 由于议会的席位总数是整数,当然,通常不可能精确地按比例分配席位。 在 JAG Kingdom 中,使用以下方法(称为 D'Hondt 方法)来确定每一方的席位数。
假设每个政党都有无限的候选人供应,并且每个政党的候选人都以某种方式排序。 对于获得 $x$ 票的政党的第 $y$ 候选人,分配值 $\dfrac{x}{y}$。 然后,所有候选者按照其指定值的降序排列。 第一个 $T$ 候选人被视为获胜,其中 $T$ 是席位总数, 一个政党赢得的席位数就是其获胜候选人的数量。
下表显示了三个参与方的示例。 第一方获得 40 美元选票,第二方获得 60 美元选票,第三方获得 30 美元选票。 如果席位总数为$T = 9$,则第一方将赢得$3$席位,第二方将赢得$4$席位,第三方将赢得$2$席位。
[原图]
选择获奖候选人时,通过抽签打破平局;任何平局的候选人都有机会获胜。 例如,在上面的示例中,如果 $T = 5$,则两个候选者的值是 $20$,并且有两种可能的结果:
第一方赢得 $2$ 席位,第二方赢得 $2$ 席位,第三方赢得 $1$ 席位。
第一方赢得 $1$ 席位,第二方赢得 $3$ 席位,第三方赢得 $1$ 席位。
您刚刚在电视上听到了选举结果。 知道有效选票总数和每个政党赢得的席位数后,您想知道每个政党获得了多少票。
给定 $N$、$M$ 和 $S_i$ ($1 \le i \le M$), 分别表示有效选票总数、政党数量以及第$i$个政党赢得的席位数, 您的任务是确定每个政党获得的最小和最大可能票数。 请注意,在某些情况下,给定的 $N$、$M$ 和 $S_i$ 可能不存在这种情况。
输入
输入的第一行包含两个整数 $N$ ($1 \le N \le 10^9$) 和 $M$ ($1 \le M \le 30{,}000$), 其中$N$是有效选票总数,$M$是政党数量。 接下来是 $M$ 行,其中第 $i$ 行包含单个整数 $S_i$ ($0 \le S_i \le 30{,}000$), 代表第 $i$ 党赢得的席位数。 您可以假设存在 $i$ 且 $S_i \ne 0$。
输出
如果不存在给定的$N$、$M$和$S_i$的情况,则显示“不可能”一词。 否则,输出 $M$ 行,每行包含两个整数。 第 $i$ 行中的第一个整数和第二个整数 应分别是第 $i$ 方获得的最小和最大可能票数。
示例输入 1
10 2 2 1
样本输入 1 的输出
5 7 3 5
示例输入 2
5 6 0 2 0 2 6 0
样本输入 2 的输出
0 0 1 1 0 0 1 1 3 3 0 0
示例输入 3
2000 5 200 201 202 203 204
样本输入 3 的输出
396 397 397 399 399 401 401 403 403 404
示例输入 4
15 10 1 1 1 1 1 1 1 1 1 13
样本输入 4 的输出
impossible
示例输入 5
1000000000 9 12507 16653 26746 21516 29090 10215 28375 21379 18494
样本输入 5 的输出
67611619 67619582 90024490 90033301 144586260 144597136 116313392 116323198 157257695 157269050 55221291 55228786 153392475 153403684 115572783 115582561 99976756 99985943