울타리 칠하기

면접 대비

시간 제한1초메모리 제한1024 MB

요약

칠해진 집 번호들과 거리 K가 주어질 때, 칠해진 집에서 K 이내에 있지만 아직 칠해지지 않은 집을 오름차순으로 출력합니다. 연속된 번호는 시작..끝 형식으로 묶습니다.

난이도: 보통10점 중 4점
유형: 정렬, 구간, 구현
정답자: 아직 제출이 없습니다

문제

Tom Sawyer는 또 큰 말썽을 일으켰고, Polly 이모는 그에게 울타리를 칠하게 하려 한다. Tom과 그의 못된 친구들의 울타리는 이미 모두 칠해졌고, 몇몇은 여러 번 칠해졌다. 이제는 그들의 이웃 울타리를 칠해야 한다.

Tom이 사는 거리에서 집들은 길 한쪽에 늘어서 있고, 1부터 시작하는 연속된 정수로 번호가 매겨져 있다. Polly 이모는 Tom의 집이나 그의 친구 집에서 거리가 $K$ 이하인 모든 집의 울타리를 다시 칠하도록 하려 한다.

입력

첫 줄에는 정수 $K$ ( $1 \le K \le 10^7$ )가 주어진다. 둘째 줄에는 이미 칠해진 울타리의 개수 $N$ ( $1 \le N \le 10^5$ )이 주어진다. 다음 $N$ 개 줄에는 이미 울타리가 칠해진 집의 번호 $M_i$ 가 한 줄에 하나씩 주어진다 ( $1 \le M_i < 2^{63} - K$ ).

출력

아직 칠해지지 않은 울타리를 가진 집 중에서, 칠해진 울타리가 있는 집과의 거리가 $K$ 이하인 집의 번호를 오름차순으로 출력한다. 목록이 길 수 있으므로, 연속된 두 개 이상의 번호는 한 줄에 첫 번호, 두 점, 마지막 번호로 줄여서 출력한다.

예제2

예제 1
입력
```
3
2
10
13
```
예상 출력
```
7..9
11..12
14..16
```
예제 2
입력
```
2
3
5
10
12
```
예상 출력
```
3..4
6..9
11
13..14
```