재생 목록 표시 구간

이고르는 컴퓨터에 1번부터 N번까지 번호가 붙은 노래를 아주 많이 가지고 있다. 화면에는 모든 노래를 한 번에 보여 줄 수 없어서, 어떤 노래 S를 재생할 때는 S를 포함하는 연속한 K개의 노래만 화면에 표시된다.

어떤 노래가 처음 화면에 나타나면 프로그램은 그 노래 파일을 열어 가수와 제목 같은 메타데이터를 읽어야 한다. 한 번 읽은 메타데이터는 메모리에 저장되므로, 같은 노래가 나중에 다시 화면에 나타나도 파일을 다시 열 필요가 없다.

이고르가 들을 노래들이 순서대로 주어진다. 각 노래가 재생될 때 화면에 표시할 연속 구간을 하나씩 정하라. 모든 재생이 끝날 때까지 파일을 열어야 하는 서로 다른 노래 수가 최소가 되어야 한다.

최적해는 여러 개일 수 있다.

첫째 줄에 두 정수 N과 K가 주어진다. N은 전체 노래 수, K는 화면에 표시되는 노래 수이다.

둘째 줄에 이고르가 들을 노래 수 M이 주어진다.

다음 M개의 줄에는 재생할 노래 번호가 순서대로 하나씩 주어진다. 모든 노래 번호는 1 이상 N 이하이고, 같은 노래는 두 번 이상 주어지지 않는다.

제한은 다음과 같다.

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

총 M+1개의 줄을 출력한다.

첫째 줄에는 파일을 열어야 하는 서로 다른 노래 수의 최솟값을 출력한다.

그다음 M개의 줄에는 입력으로 주어진 각 노래 S에 대해 두 정수 A와 B를 출력한다. 이는 S가 재생될 때 화면에 A번부터 B번까지의 노래가 표시된다는 뜻이다. 각 줄은 다음 조건을 만족해야 한다.

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