Segmentland 最近发生了一场革命。新政府致力于实现平等，他们雇佣你来帮助该国进行土地重新分配。

Segmentland 是一个长度为 $l$ 公里的线段，首都位于其一端。Segmentland 有 $n$ 位公民，第 $i$ 位公民的家位于距离首都 $a_i$ 公里的位置。没有两户人家位于同一个点。每位公民都应获得一个正长度的线段，其端点距离首都为整数，且该线段包含其家。这些线段的并集应为整个 Segmentland，且除了端点外，它们不应有公共点。为了确保平等，最长线段与最短线段长度之差应尽可能小。

输入格式

第一行包含两个整数 $l$ 和 $n$ ($2 \le l \le 10^9$; $1 \le n \le 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 \le s_i < f_i \le l$)，每行一对。第 $i$ 行的数字对表示第 $i$ 位公民获得的线段 $[s_i, f_i]$ 的端点。

如果存在多种使最长线段与最短线段长度之差相同的方案，你可以输出其中任意一种。

样例

输入 1

6 3
1 3 5

输出 1

0 2
2 4
4 6

说明

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

输入 2

10 2
1 2

输出 2

0 2
2 10

说明

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