← 返回题目列表

Codeforces · 1666/E

E. 均匀分割

中文机器翻译题面 查看原题

星域大陆最近发生了一场革命。新政府致力于平等,他们聘请你来帮助该国的土地重新分配。

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。