Description

Segmentland 是一个长度为 $l$ 公里的线段，首都位于其一端。该国共有 $n$ 位公民，第 $i$ 位公民的家位于距离首都 $a_i$ 公里的点上。所有公民的居住点都不相同。每位公民应该获得一个长度为正的线段，其端点与首都的距离为整数，且必须包含她自己的家。这些线段的并集必须覆盖整个 Segmentland，且它们之间除了端点外不能有重叠部分。为了确保平等，最长线段与最短线段的长度差应尽可能小。

Input Format

输入的第一行包含两个整数 $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$）。

Output Format

输出 $n$ 对数 $s_i, f_i$（$0 \leq s_i < 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

Hint

在第一个样例中，可以使所有线段长度相等。

在第二个样例中，公民居住点靠近首都，因此最短线段长度为 2，最长线段长度为 8。

翻译由 DeepSeek V3 完成