题目描述

在JAG王国中，进行了一次选举，选出了议会的成员。这个国家只采用政党比例代表制。在这个制度中，每个公民投票给一个政党，一个政党赢得的席位数量将与其获得的选票数量成比例。由于议会的总席位数是整数，当然，往往无法完全按比例分配席位。在JAG王国，使用称为D'Hondt方法的以下方法来确定每个政党的席位数。

假设每个政党都有无限多的候选人，并且每个政党的候选人按某种方式排序。对于获得x票的第y位候选人，分配值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没有这样的情况，请显示单词"impossible"。否则，输出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

来源

Japan Alumni Group Spring Contest 2014