Problem Description

Igor has a playlist containing $n$ songs, numbered from $1$ to $n$. Today he is going to listen to $m$ songs.

When playing the $i$-th song, the information of $k$ consecutive songs will be shown in a list. These $k$ consecutive songs must include the $i$-th song, and there are no other requirements.

When a song is shown in the list, its information will be read once. If a song is shown in the list multiple times, its information will only be read once (no matter whether the two displays are consecutive).

Please give a plan that makes the number of songs whose information gets read as small as possible.

Input Format

The first line contains two integers, representing the number of songs in the playlist $n$ and the given parameter $k$.

The second line contains one integer, representing the number of songs Igor will listen to, $m$.

Lines $3$ to $(m + 2)$ each contain one integer, representing the index $a_i$ of the $i$-th song Igor will listen to.

Output Format

This problem uses a Special Judge.

In the first line, output an integer $t$, the minimum number of times song information is read.

In lines $2$ to $(m + 1)$, output two integers per line. On line $(i + 1)$, output $l_i, r_i$, meaning that when listening to the $i$-th song, the information of songs from $l_i$ to $r_i$ is displayed.

Your output must satisfy $r_i - l_i + 1 = k$, $1 \leq l_i \lt r_i \leq n$, and the number of songs read according to your plan is $t$.

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

Hint

Constraints

For all test cases, it is guaranteed that:

• $1 \leq k \lt n \leq 10^9$, $1 \leq m \leq 3 \times 10^5$.
• $1 \leq a_i \leq n$, and all $a_i$ are pairwise distinct.

Scoring

• If the number of output numbers is less than $(2 \cdot m + 1)$, or the number $t$ in the first line is different from the answer, you will get $0\%$ of the score for that test point.
• If $t$ is the same as the answer but the output plan is incorrect, you will get $50\%$ of the score for that test point.
• If $t$ is the same as the answer and the output plan is correct, you will get $100\%$ of the score for that test point.

Notes

This problem is translated from COCI2007-2008 COI2008 T2 KOLEKCIJA. The translation and SPJ are provided by 一扶苏一.

Translated by ChatGPT 5