벽에 숫자가 1부터 N까지 순서대로 적혀 있다. 당신은 창문을 통해 M개의 숫자들을 순서대로 보려고 한다. 그런데 창문이 너무 작기 때문에 정확히 K개의 수만을 볼 수 있다. 당신은 창문을 좌우로 밀면서 M개의 숫자들을 순서대로 보게 될 것이다.

그런데, 숫자를 보다 보면 본의 아니게 다른 숫자도 보게 된다. 당신은 이를 비효율적이라고 여기기 때문에 최대한 적은 개수의 숫자를 보려고 한다. 숫자를 보는 방법을 구하는 프로그램을 작성하여라.

입력

• 첫 번째 줄에는 숫자의 개수 N과 창문의 크기 K가 주어진다. (1 ≤ K < N ≤ 1,000,000,000)
• 두 번째 줄에는 당신이 보아야 할 숫자의 개수 M이 주어진다. (1 ≤ M ≤ 300,000)
• 세 번째 줄부터 M개의 줄에는 당신이 보아야 할 숫자가 차례대로 주어진다.

출력

• 첫 번째 줄에는 보게 되는 숫자의 개수의 최솟값을 출력한다.
• 두 번째 줄부터 M개의 줄에는 A, B를 출력하는데, 주어진 수를 보기 위해서 창문을 밀 때, 보게 되는 숫자가 A 이상 B 이하라는 말이다.

입출력 예

입력

10 3
5
4
5
8
7
6

출력

5
4 6
4 6
6 8
6 8
6 8

입력

15 4
6
6
14
11
3
8
5

출력

10
3 6
11 14
11 14
3 6
5 8
3 6

입력

1000 301
3
300
500
700

출력

401
300 600
350 650
400 700

출처:2007-2008/coci/
번역:functionx