Problem Description

Igor has a playlist containing \( n \) songs, numbered from \( 1 \) to \( n \). Today, he plans to listen to \( m \) songs.

When playing the \( i \)-th song, the information of \( k \) consecutive songs is displayed on a list, which must include the \( i \)-th song, with no other requirements.

When a song is displayed on the list, its information is read once. If a song is displayed multiple times on the list, its information is only read once (regardless of whether the displays are consecutive).

Provide a scheme that minimizes the number of times the system reads the song information.

Input Format

The first line contains two integers, representing the number of songs \( n \) in the playlist and the parameter \( k \).

The second line contains an integer, representing the number of songs \( m \) Igor plans to listen to.

From the third to the \((m + 2)\)-th line, each line contains an integer, representing the number \( a_i \) of the \( i \)-th song Igor plans to listen to.

Output Format

This problem includes a Special Judge.

The first line should output an integer \( t \), representing the minimum number of times the song information is read.

From the second to the \((m + 1)\)-th line, each line should contain two integers \( l_i \) and \( r_i \), representing that when listening to the \( i \)-th song, the information from the \( l_i \)-th to the \( r_i \)-th song is displayed.

Your output must ensure \( r_i - l_i + 1 = k \), \( 1 \leq l_i < r_i \leq n \), and the number of songs read according to your scheme is \( t \).

Sample Input and Output

Sample Input #1

10 3
5
4
5
8
7
6

Sample Output #1

5 
4 6 
4 6 
6 8 
6 8 
6 8

Sample Input #2

15 4
6
6
14
11
3
8
5

Sample Output #2

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

Sample Input #3

1000 301
3
300
500
700

Sample Output #3

401
300 600
350 650
400 700

Notes

Data Size and Constraints

For all test cases, the following constraints are guaranteed:

• \( 1 \leq k < n \leq 10^9 \), \( 1 \leq m \leq 3 \times 10^5 \).
• \( 1 \leq a_i \leq n \), and \( a_i \) are distinct.

Scoring Criteria

• If the output has fewer than \((2 \cdot m + 1)\) numbers, or the first number \( t \) in the output differs from the answer, you will receive \( 0\% \) of the points for that test case.
• If \( t \) matches the answer but the output scheme is incorrect, you will receive \( 50\% \) of the points for that test case.
• If \( t \) matches the answer and the output scheme is correct, you will receive \( 100\% \) of the points for that test case.

Notes

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

见题面 Input 部分

见题面 Output 部分