Description

四川火锅是全世界最著名的美食之一。人们都喜欢它辛辣的味道。

现在有 $n$ 位游客，编号从 $0$ 到 $n-1$，围坐在火锅旁边。一共有 $k$ 种火锅食材，第 $i$ 位游客最喜欢的食材是 $a_i$。一开始，每位游客的幸福值为 $0$，火锅里是空的。

游客们会依次进行 $m$ 次操作，第 $i$ 次（编号从 $0$ 到 $m-1$）由编号为 $i\bmod n$ 的游客执行。每当游客 $t$ 操作时：

• 如果火锅中已有食材 $a_t$，他会把这些食材都吃掉，幸福值增加 $1$。
• 否则，他会向火锅中加入一份食材 $a_t$，幸福值不变。

你的任务是计算每位游客在 $m$ 次操作后各自的幸福值。

Input Format

有多组测试数据。输入的第一行为整数 $T$，表示测试数据组数，$1 \le T \le 10^3$。对于每组测试数据：

第一行包含三个整数 $n, k, m$，$1 \le n \le 10^5$，$1 \le k \le 10^5$，$1 \le m \le 10^9$，分别表示游客人数、食材种类数和操作次数。

第二行包含 $n$ 个整数 $a_0, a_1, \cdots, a_{n-1}$，$1 \le a_i \le k$，其中 $a_i$ 表示第 $i$ 位游客最喜欢的食材编号。

保证所有测试数据中 $n$ 的总和和 $k$ 的总和均不超过 $2 \times 10^5$。

Output Format

对于每组测试数据，输出 $n$ 个用空格隔开的整数 $h_0, h_1, \cdots, h_{n-1}$，其中 $h_i$ 表示第 $i$ 位游客在 $m$ 次操作后获得的幸福值。

请不要在每行末尾输出多余的空格，否则答案可能会被判为错误！

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

0 2 1
2
2 2
0 5

Hint

第一个示例的执行过程如下：

$$\begin{array}{|c|c|c|c|} \hline \textbf{操作} & \textbf{游客} & \textbf{操作内容} & \textbf{操作后火锅状态} \\ \hline 0 & 0 & 向火锅中加入食材 1 & \{1\} \\ \hline 1 & 1 & 吃掉火锅中的食材 1 & \{\} \\ \hline 2 & 2 & 向火锅中加入食材 2 & \{2\} \\ \hline 3 & 0 & 向火锅中加入食材 1 & \{1, 2\} \\ \hline 4 & 1 & 吃掉火锅中的食材 1 & \{2\} \\ \hline 5 & 2 & 吃掉火锅中的食材 2 & \{\} \\ \hline \end{array}$$

由 ChatGPT 5 翻译