Description

Input

The first line of the input contains two integers $l$ and $n$ ($2 \leq l \leq 10^9; 1 \leq n \leq 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 < a_1 < a_2 < \dots < a_n < l$).

Output

Output $n$ pairs of numbers $s_i, f_i$ ($0 \leq s_i < f_i \leq l$), one pair per line. The pair on $i$-th line denotes the ends of the $[s_i, f_i]$ segment that $i$-th citizen receives.

If there are many possible arrangements with the same difference between the lengths of the longest and the shortest segments, you can output any of them.

6 3
1 3 5

0 2
2 4
4 6

10 2
1 2

0 2
2 10

Note

In the first example, it is possible to make all segments equal. Viva la revolucion!

In the second example, citizens live close to the capital, so the length of the shortest segment is 2 and the length of the longest segment is 8.