星域大陆最近发生了一场革命。新政府致力于平等,他们聘请你来帮助该国的土地重新分配。
Segmentland 是一段长度 $$$l$$$ 公里的路段,首都位于其一端。 Segmentland 有 $$$n$$$ 位公民,第 $$$i$$$ 位公民的家位于距首都 $$$a_i$$$ 公里处。没有两栋房屋位于同一地点。每个公民都应该收到一段正长度的线段,其末端距其所在首都的整数距离。这些片段的联合应该是整个Segmentland,并且除了它们的末端之外,它们不应该有共同点。为了确保相等,最长线段和最短线段的长度之间的差异应尽可能小。
输入
输入的第一行包含两个整数 $$$l$$$ 和 $$$n$$$ ($$$2 \leq l \leq 10^9; 1 \leq n \leq 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \lt a_1 \lt a_2 \lt \dots \lt a_n \lt l$$$)。
输出
输出 $$$n$$$ 数字对 $$$s_i, f_i$$$ ($$$0 \leq s_i \lt f_i \leq l$$$),每行一对。第 $$$i$$$ 行上的对表示第 $$$i$$$ 公民收到的 $$$[s_i, f_i]$$$ 段的末端。
如果有多种可能的排列,且最长和最短线段的长度差异相同,则可以输出其中任何一个。
示例
输入复制
6 3 1 3 5
输出复制
0 2 2 4 4 6
输入复制
10 2 1 2
输出复制
0 2 2 10
注意
在第一个示例中,可以使所有段相等。 革命万岁!
在第二个示例中,公民居住在首都附近,因此最短线段的长度为 2,最长线段的长度为 8。