408419: GYM103117 B Hotpot

Sichuan hotpot is one of the most famous dishes around the world. People love its spicy taste.

There are $$$n$$$ tourists, numbered from $$$0$$$ to $$$(n-1)$$$, sitting around a hotpot. There are $$$k$$$ types of ingredients for the hotpot in total and the $$$i$$$-th tourist favors ingredient $$$a_i$$$ most. Initially, every tourist has a happiness value of $$$0$$$ and the pot is empty.

The tourists will perform $$$m$$$ moves one after another, where the $$$i$$$-th (numbered from $$$0$$$ to $$$(m - 1)$$$) move is performed by tourist $$$(i \mod n)$$$. When tourist $$$t$$$ moves:

• If ingredient $$$a_t$$$ exists in the pot, he will eat them all and gain $$$1$$$ happiness value.
• Otherwise, he will put one unit of ingredient $$$a_t$$$ into the pot. His happiness value remains unchanged.

Your task is to calculate the happiness value for each tourist after $$$m$$$ moves.

There are multiple test cases. The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 10^3$$$) indicating the number of test cases. For each test case:

The first line contains three integers $$$n$$$, $$$k$$$ and $$$m$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le k \le 10^5$$$, $$$1 \le m \le 10^9$$$) indicating the number of tourists, the number of types of ingredients and the number of moves.

The second line contains $$$n$$$ integers $$$a_0, a_1, \cdots, a_{n-1}$$$ ($$$1 \le a_i \le k$$$) where $$$a_i$$$ indicates the favorite ingredient of tourist $$$i$$$.

It's guaranteed that neither the sum of $$$n$$$ nor the sum of $$$k$$$ of all the test cases will exceed $$$2 \times 10^5$$$.

For each test case output $$$n$$$ integers $$$h_0, h_1, \cdots, h_{n-1}$$$ in one line separated by a space, where $$$h_i$$$ indicates the happiness value of tourist $$$i$$$ after $$$m$$$ moves.

Please, DO NOT output extra spaces at the end of each line, or your answer might be considered incorrect!

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

The first sample test case is explained as follows: