CF1666E Even Split

Segmentland 是一段长度为 $l$ 公里的线段，首都位于其一端。有 $n$ 位公民居住在 Segmentland，第 $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 < a_1 < a_2 < \dots < a_n < l$）。

输出 $n$ 行，每行两个整数 $s_i, f_i$（$0 \leq s_i < f_i \leq l$），表示第 $i$ 位公民获得的区间 $[s_i, f_i]$ 的两个端点。 如果存在多种分配方式且最长与最短区间长度之差相同，你可以输出其中任意一种。

在第一个样例中，可以让所有区间长度相等。  在第二个样例中，公民们都住在靠近首都的地方，因此最短区间长度为 2，最长区间长度为 8。  由 ChatGPT 4.1 翻译