售票处出售音乐会门票。售票处不单独出售单张门票，而是以固定数量的连座形式出售。售票处收到了大量的购票订单。每份订单指定了该连座中编号最小的座位号。

售票处可能无法满足所有的购票订单。此外，如果仅按照订单请求分配座位，可能会有大量座位空置。因此，售票处采取了以下分配和定价策略：如果一份订单被接受，且分配的座位与请求的座位完全一致，则购买者支付全价（每组 2 个 petaks）；如果一份订单被接受，但分配的座位与请求的座位不一致（至少有一个位置不同），则购买者支付半价（每组 1 个 petak）。

目标是最大化总收入。

任务

你需要编写一个程序，计算可以实现的最大收入（子任务 A），并给出实现该收入的订单座位分配方案（子任务 B）。

输入格式

输入文件的第一行包含两个整数 $M$ 和 $L$。$M$ ($1 \le M \le 30\,000$) 是座位总数，$L$ ($1 \le L \le 100$) 是每组连座的座位数。座位编号从 $1$ 到 $M$。第二行包含一个整数 $N$ ($1 \le N \le 100\,000$)，表示购票订单的数量。第三行包含 $N$ 个整数，定义了购票订单。第 $i$ 个数字 $z$ ($1 \le z \le M-L+1$) 表示第 $i$ 位购买者请求的是从座位 $z$ 开始到 $z+L-1$ 结束的连座。

输出格式

输出文件的第一行包含一个整数 $S$，即最大收入（子任务 A）。第二行包含一个整数 $Q$，即被接受的订单数量。接下来的 $Q$ 行描述座位分配情况（子任务 B）。每行包含一对整数 $x$ $y$。该对整数 $x$ $y$ 表示第 $x$ 位购买者获得了从座位编号 $y$ 开始的连座。输出行必须按座位编号递增的顺序排列。

如果存在多种可能性，你的程序只需输出其中一种即可。

样例

输入 1

20 3
7
4 2 10 9 16 15 17

输出 1

9
6
4 1
1 4
2 7
3 10
6 13
5 16