四川火锅是世界上最著名的菜肴之一。人们喜爱它辛辣的味道。

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

游客们将依次进行 $m$ 次操作，其中第 $i$ 次（编号从 $0$ 到 $(m-1)$）操作由游客 $(i \pmod n)$ 执行。当游客 $t$ 进行操作时：

• 如果火锅中存在食材 $a_t$，他会吃掉锅中所有的该食材，并获得 $1$ 点幸福值。
• 否则，他会向火锅中放入一个单位的食材 $a_t$。他的幸福值保持不变。

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

输入格式

输入包含多组测试数据。第一行包含一个整数 $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, \dots, a_{n-1}$ ($1 \le a_i \le k$)，其中 $a_i$ 表示游客 $i$ 最喜欢的食材。

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

输出格式

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

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

样例

输入 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

说明

第一个样例测试数据解释如下：

• 移动 0：游客 0 放入食材 1，火锅状态：{1}
• 移动 1：游客 1 吃掉锅中的食材 1，火锅状态：{}
• 移动 2：游客 2 放入食材 2，火锅状态：{2}
• 移动 3：游客 0 放入食材 1，火锅状态：{1, 2}
• 移动 4：游客 1 吃掉锅中的食材 1，火锅状态：{2}
• 移动 5：游客 2 吃掉锅中的食材 2，火锅状态：{}