Description

欢迎你，初学者，加入到CEIT这个非常温暖和有爱的大家庭。

CEIT有非常多的团建活动，在结束完某场比赛后，Orange决定带领大家一起去吃火锅自助。一共有 $n$ 位成员围坐成一圈，火锅店一共有 $k$ 种食材。特别的，每个人都有一种特别喜爱的食材，当他吃到这种食材之后，其幸福指数就会增加1点。

最开始，每个人的幸福指数都是0，锅内一开始没有任何食材。从第1个人开始，每个人都会按照特定的规则来涮火锅，当最后1个人结束后，又会回到第1个人重新开始，一共进行 $m$ 轮(每个人操作1次算1轮)。涮火锅的规则如下：

• 轮到第 $i$ 位成员时，他首先会检查火锅内是否有他特别喜爱的食材 $a_i$。
• 如果有，则他会夹出这份食材并且吃掉，此时，其幸福指数会增加1。如果没有，则他会点一份 $a_i$ 并将其下入锅内，此时，其幸福指数不变。

现在，作为负责人的Orange需要统计各位成员的幸福指数来判断这是否是一次成功的团建，请你帮助他完成这个任务。

Format

Input

输入第一行包含3个整数 $n,k,m$，分别表示成员总数，火锅店食材总数以及涮火锅的轮数。

第二行包含 $n$ 个整数 $a_i$，表示第 $i$ 位成员最喜爱的食材编号。

数据范围

$1 \le n,k \le 10^5$

$1 \le m \le 10^9$

$1 \le a_i \le k$

Output

输出 $n$ 个整数，第 $i$ 个整数代表第 $i$ 位成员最终的幸福指数。

Samples

3 2 6
1 1 2

0 2 1

1 1 5
1

2

2 2 10
1 2

2 2

2 2 10
1 1

0 5

Note

对于第一个样例，其具体过程如下表格所示：