#2857. [Ceoi2012]jobs

题目描述

在接下来的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。