题目描述

Igor 有一个包含 $n$ 首歌的歌单，歌曲从 $1$ 至 $n$ 编号，他今天要听 $m$ 首歌。

当播放第 $i$ 首歌时，连续 $k$ 首歌的信息会被显示在一个列表上，这连续 $k$ 首歌必须包含第 $i$ 首歌，但是没有其他要求。

当一首歌被显示在列表上时，它的信息会被读取一次。如果一首歌多次被显示在列表上，他的信息也只会被读取一次（无论两次显示是否连续）。

请给出一种方案，使得系统读取歌曲信息的次数最少。

输入格式

第一行有两个整数，分别表示歌单的歌曲数 $n$ 和给定的参数 $k$。

第二行有一个整数，表示 Igor 要听的歌曲数 $m$。

第 $3$ 到第 $(m + 2)$ 行，每行一个整数，表示 Igor 要听的第 $i$ 首歌的编号 $a_i$。

输出格式

本题存在 Special Judge。

请在第一行输出一个整数 $t$，表示读取歌曲信息的最少次数。

第 $2$ 到第 $(m + 1)$ 行，每行两个整数，第 $(i + 1)$ 行的 $l_i, r_i$，表示听第 $i$ 首歌的时候显示第 $l_i$ 到第 $r_i$ 首歌的信息。

你的输出需要保证 $r_i - l_i + 1 = k$，$1 \leq l_i \lt r_i \leq n$，且按照你给出的方案读取的歌曲数为 $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

提示

数据规模与约定

对于全部的测试点，保证：

• $1 \leq k \lt n \leq 10^9$，$1 \leq m \leq 3 \times 10^5$。
• $1 \leq a_i \leq n$，$a_i$ 互不相同。

计分标准

• 如果输出的数字不足 $(2 \cdot m + 1)$ 个，或输出第一行的数字 $t$ 与答案不同，则获得测试点 $0\%$ 的分数。
• 如果 $t$ 与答案相同，输出方案错误，则获得该测试点 $50\%$ 的分数。
• 如果 $t$ 与答案相同，且输出方案正确，则获得该测试点 $100\%$ 的分数。

说明

题目译自 COCI2007-2008 COI2008 T2 KOLEKCIJA，翻译与 SPJ 均来自一扶苏一。