407509: GYM102821 A Autochess

Fish likes playing games, and recently he is addicted to Autochess.

There are $$$N$$$ spots (initially empty) in a line named waiting zone, and Fish can add some chessmen into it. Each spot can be occupied by exactly one chessman and each chessman has a name and a level tag (1,2 or 3). Whenever Fish decides to add a chessman named $$$s$$$ of level 1 into the waiting zone, some routines will be on process in order:

• Firstly, if there is a chessman named $$$s$$$ of level 3 in the waiting zone, Fish's operation fails and the process continue(skip following operations and move to add next chessmen).
• Secondly, if there are already $$$K-1$$$ chessmen named $$$s$$$ of level $$$1$$$ in the waiting zone, all these chessmen will be removed and the chessman Fish holds will upgrade to level 2, and if at this time there are already $$$K-1$$$ chessmen named $$$s$$$ of level $$$2$$$, all these chessmen will be removed and the chessman Fish holds will upgrade to level 3.
• Finally, if there are any spots available, the chessman Fish holds will be placed in the leftmost one.

Fish decides to add $$$M$$$ chessmen of level 1 into the waiting zone, so please help him figure out the final status of the waiting zone.

The first line of input contains an integer $$$T$$$, representing the number of test cases.

Then for each test case:

The first line contains three integers $$$M, N, K$$$, the number of chessmen Fish wants to add, the number of spots in waiting zone and the parameter in the process.

Then $$$M$$$ lines follow, each line containing a string $$$s$$$ consisting of only lowercase Latin characters, which is the name of chessman Fish wants to add.

For each test case, you should output Case $$$x$$$: first, where $$$x$$$ indicates the case number starting from $$$1$$$. Then $$$N$$$ strings separated by one space follow, representing the final status of the waiting zone. Each string is the combination of the name and the level tag of the chessman in that spot: for those of level 1, use the name only; for those of level 2 or 3, use the name followed by an extra 2 or 3 respectively. If one spot is empty, print -1 instead.

2
9 7 3
axe
axe
jugg
axe
jugg
jugg
mars
axe
axe
10 7 2
axe
axe
jugg
axe
jugg
jugg
mars
axe
axe
mars

Case 1: axe2 jugg2 mars axe axe -1 -1
Case 2: axe3 jugg2 mars2 jugg -1 -1 -1

$$$1 \le T \le 100$$$

$$$1 \le N, M\le 10^5$$$

$$$2 \le K \le N$$$

Length of $$$s$$$ will not exceed $$$10$$$

For $$$90\%$$$ test cases: $$$1 \le N, M, K \le 1000$$$