P14118 [SCCPC 2021] 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 \bmod 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!

The first sample test case is explained as follows: $$ \begin{array}{|c|c|c|c|} \hline \textbf{Move} & \textbf{Tourist} & \textbf{Action} & \textbf{Pot after move} \\ \hline 0 & 0 & \text{Puts ingredient 1 into the pot} & \{1\} \\ \hline 1 & 1 & \text{Eats ingredient 1 in the pot} & \{\} \\ \hline 2 & 2 & \text{Puts ingredient 2 into the pot} & \{2\} \\ \hline 3 & 0 & \text{Puts ingredient 1 into the pot} & \{1, 2\} \\ \hline 4 & 1 & \text{Eats ingredient 1 in the pot} & \{2\} \\ \hline 5 & 2 & \text{Eats ingredient 2 in the pot} & \{\} \\ \hline \end{array} $$