#P14118. [SCCPC 2021] Hotpot

[SCCPC 2021] Hotpot

题目描述

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

There are nn tourists, numbered from 00 to (n1)(n-1), sitting around a hotpot. There are kk types of ingredients for the hotpot in total and the ii-th tourist favors ingredient aia_i most. Initially, every tourist has a happiness value of 00 and the pot is empty.

The tourists will perform mm moves one after another, where the ii-th (numbered from 00 to (m1)(m - 1)) move is performed by tourist (imodn)(i \bmod n). When tourist tt moves:

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

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

输入格式

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

The first line contains three integers nn, kk and mm (1n1051 \le n \le 10^5, 1k1051 \le k \le 10^5, 1m1091 \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 nn integers a0,a1,,an1a_0, a_1, \cdots, a_{n-1} (1aik1 \le a_i \le k) where aia_i indicates the favorite ingredient of tourist ii.

It's guaranteed that neither the sum of nn nor the sum of kk of all the test cases will exceed 2×1052 \times 10^5.

输出格式

For each test case output nn integers h0,h1,,hn1h_0, h_1, \cdots, h_{n-1} in one line separated by a space, where hih_i indicates the happiness value of tourist ii after mm 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:

$$\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} $$