Fence Painting

Interview

Time limit1sMemory limit1024 MB

Summary

Given painted house numbers and a distance K, list the unpainted houses within K of a painted house, merging consecutive runs as a..b.

Level: Medium4 of 10
Topics: Sorting, Intervals, Implementation
Solved: No attempts yet

Problem

Tom Sawyer got into big trouble again, so Aunt Polly wants to send him out to paint the fence. The fences of Tom and his bad friends have all been repainted already, and some of them more than once. Now the fences of their neighbors must be painted.

The houses on the street where Tom lives stand on one side of the street and are numbered with consecutive integers starting from 1. Aunt Polly decides to have the fences repainted for every house that is at distance at most $K$ from Tom's house or from one of his friends' houses.

Input

The first line contains an integer $K$ ( $1 \le K \le 10^7$ ). The second line contains the number of already painted fences $N$ ( $1 \le N \le 10^5$ ). Each of the next $N$ lines contains the number $M_i$ of a house whose fence is already painted, one number per line ( $1 \le M_i < 2^{63} - K$ ).

Output

Print, in increasing order, the numbers of the houses whose fences are not painted yet and that are at distance at most $K$ from a house with a painted fence. The list can be long, so compress it: instead of printing two or more consecutive house numbers separately, print the first number, two dots, and the last number on one line.

Examples2

Example 1
Input
```
3
2
10
13
```
Expected output
```
7..9
11..12
14..16
```
Example 2
Input
```
2
3
5
10
12
```
Expected output
```
3..4
6..9
11
13..14
```