Playlist Display Intervals

Igor has a very large music collection on his computer. The songs are numbered from 1 to N. The screen cannot show the whole collection at once, so when song S is playing, the screen shows exactly K consecutive songs and that block must include S.

When a song appears on the screen for the first time, the program must open its file and read metadata such as the artist and title. After that metadata is stored in memory, the same song can appear again without opening the file again.

You are given the songs Igor will listen to, in order. For each requested song, choose the consecutive block shown while it is playing. The number of distinct song files opened over the whole playlist must be as small as possible.

There may be more than one optimal answer.

The first line contains two integers N and K: the number of songs and the number of songs shown on the screen.

The second line contains an integer M, the number of songs Igor will listen to.

Each of the next M lines contains one requested song number, in playback order. Every song number is between 1 and N, and no song number appears more than once.

Constraints:

• 1 <= K < N < 1,000,000,000
• 1 <= M <= 300,000

Print M+1 lines.

On the first line, print the minimum possible number of distinct song files that must be opened.

Then print M lines, one for each requested song S in input order. On each line print two integers A and B, meaning that songs A through B are shown while S is playing. Each line must satisfy:

• 1 <= A <= S <= B <= N
• B - A + 1 = K