[Ceoi2012]jobs

时间限制:20s      空间限制:128MB

题目描述

在接下来的N天内,你收到了M个生产请求,每天可能受到多个请求。原则上来说,第i天收到的生产请求只能在第i天完成,但是实际中,你可以最多推迟D天完成请求,即在第i天到i + D天内完成都可以。进行生产需要使用一种机器,一台机器一天内可以完成一个生产请求。你的任务是计算出最少需要的机器台数,使得所有生产都能按要求完成


输入格式

第一行三个非负整数N, M, D (0 ≤ D < N)。
第二行M个正整数,第i个正整数表示在第几天收到了第i个请求。生产请求用正整数1..M编号。数据保证第N-D天之后不会收到生产请求。


输出格式

第一行一个正整数,表示最少需要的机器个数。下面N行给出每天完成的请求编号。每一行以0结束。如果存在多种方案,随意输出一种即可。


样例输入

8 2 12
1 2 4 2 1 3 5 6 2 3 6 4

样例输出

2
5 1 0
9 4 0
2 10 0
6 12 0
3 7 0
11 8 0
0
0

提示

对于100%的数据满足:1 ≤ N ≤ 100,000,1 ≤ M ≤ 1,000,000。


题目来源

鸣谢Oimaster,Spj程序by liutian

Menuappsclose