B. Hotpot
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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$$$.

Output

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!

Example
Input
4
3 2 6
1 1 2
1 1 5
1
2 2 10
1 2
2 2 10
1 1
Output
0 2 1
2
2 2
0 5
Note

The first sample test case is explained as follows:

MoveTouristActionPot after move
00Puts ingredient 1 into the pot$$$\{1\}$$$
11Eats ingredient 1 in the pot$$$\{\}$$$
22Puts ingredient 2 into the pot$$$\{2\}$$$
30Puts ingredient 1 into the pot$$$\{1, 2\}$$$
41Eats ingredient 1 in the pot$$$\{2\}$$$
52Eats ingredient 2 in the pot$$$\{\}$$$