题目描述

有一个传送带上，放置了 $N$ 盘寿司。每一盘寿司具有一种品类，第 $i$ 盘寿司的品种为 $A_i$。

你有 $M$ 个打包盒，每个打包盒最多可以放 $K$ 盘寿司。传送带启动后，寿司按照顺序送来，对每一盘寿司：

• 如果某个打包盒里存在品种一样的寿司，且这个盒子还有剩余的空间，就将寿司放到这个盒子里；
• 否则，若还有空的打包盒，则将寿司放到新盒子里；
• 否则，放弃这一盘寿司。

由于传送带构成循环，从任意一盘寿司开始打包都是有可能的。

对这 $N$ 盘寿司，请依次输出，若从 $A_i$ 开始打包，最后需要放弃多少寿司。

输入格式

• 第一行：三个整数表示 $N$、$M$ 与 $K$
• 第二行：$N$ 个整数表示 $A_1$ 到 $A_N$

输出格式

• 共 $N$ 行：每行一个整数，其中第 $i$ 行的整数表示从 $A_i$ 开始打包会放弃浪费多少盘寿司。

5 2 2
0 0 1 1 2

1
1
2
2
2

数据范围

• $30\%$ 的数据，$1\leq N\leq 1000$；
• $100\%$ 的数据，$1\leq M\leq N\leq 300,000$；
• $1\leq K\leq 300,000$
• $0\leq A_i<N$

来源

改编自 ABC337F Usual Color Ball Problems