火锅盛宴

题目描述

Y 同学组织了 $N$ 位游客参加一场火锅盛宴，游客编号为 $0$ 到 $N-1$。火锅店提供 $K$ 种不同的食材。每位游客都有自己唯一偏爱的食材，其中第 $i$ 位游客最喜欢的食材编号为 $a_i$。

盛宴开始时，每位游客的幸福度均为 $0$，火锅内是空的（不含任何食材）。

盛宴将进行 $M$ 轮操作，编号从 $0$ 到 $M-1$。在第 $j$ 轮操作中，由编号为 $t = j \bmod N$ 的游客执行动作。规则如下：

1. 检查火锅中当前是否存在食材 $a_t$。
2. 若存在：该游客将火锅中的一份食材 $a_t$ 吃掉。火锅中该食材消失，该游客的幸福度增加 $1$。
3. 若不存在：该游客向火锅中加入一份食材 $a_t$。游客的幸福度不变。

请你计算在所有 $M$ 轮操作结束后，每位游客的最终幸福度。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。

对于每组测试数据： 第一行包含三个整数 $N, K, M$，分别表示游客数量、食材种类数和总操作次数。 第二行包含 $N$ 个整数 $a_0, a_1, \dots, a_{N-1}$，依次表示第 $0$ 位到第 $N-1$ 位游客最喜欢的食材编号。

输出格式

对于每组测试数据，输出一行 $N$ 个整数，第 $i$ 个整数表示第 $i$ 位游客的最终幸福度。整数之间用空格分隔，行末不要有多余空格。

样例

样例输入 #1

4
3 2 6
1 1 2
1 1 5
1
2 2 10
1 2
2 2 10
1 1

样例输出 #1

0 2 1
2
2 2
0 5

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \le T \le 10^3$
• $1 \le N, K \le 10^5$
• $1 \le M \le 10^9$
• $1 \le a_i \le K$
• 所有测试数据的 $N$ 之和不超过 $2 \times 10^5$。
• 所有测试数据的 $K$ 之和不超过 $2 \times 10^5$。