Fish 喜欢玩游戏，最近他沉迷于《自走棋》（Autochess）。

在“等待区”（waiting zone）中有一排 $N$ 个位置（初始为空），Fish 可以向其中添加一些棋子。每个位置恰好可以容纳一个棋子，每个棋子都有一个名字和一个等级标签（1、2 或 3）。每当 Fish 决定向等待区添加一个名字为 $s$ 的 1 级棋子时，会依次执行以下流程：

• 首先，如果等待区中已经存在一个名字为 $s$ 的 3 级棋子，则 Fish 的操作失败，该流程结束（跳过后续操作，直接处理下一个棋子）。
• 其次，如果等待区中已经有 $K - 1$ 个名字为 $s$ 的 1 级棋子，则这些棋子会被移除，Fish 手中的棋子升级为 2 级；如果此时等待区中已经有 $K - 1$ 个名字为 $s$ 的 2 级棋子，则这些棋子会被移除，Fish 手中的棋子升级为 3 级。
• 最后，如果还有空位，Fish 手中的棋子将被放置在最左侧的空位中。

Fish 决定向等待区添加 $M$ 个 1 级棋子，请帮他计算等待区的最终状态。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。

对于每个测试用例： 第一行包含三个整数 $M, N, K$，分别表示 Fish 想要添加的棋子数量、等待区中的位置数量以及流程中的参数。 接下来 $M$ 行，每行包含一个仅由小写拉丁字母组成的字符串 $s$，表示 Fish 想要添加的棋子名字。

输出格式

对于每个测试用例，输出 Case x:，其中 $x$ 表示从 1 开始的用例编号。 随后输出 $N$ 个由空格分隔的字符串，表示等待区的最终状态。每个字符串是棋子名字与等级标签的组合：对于 1 级的棋子，仅使用名字；对于 2 级或 3 级的棋子，在名字后分别附加 2 或 3。如果某个位置为空，则输出 -1。

样例

样例输入 1

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

样例输出 1

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$ 字符串 $s$ 的长度不超过 10 对于 90% 的测试用例：$1 \le N, M, K \le 1000$