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:
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.
$1 <= T <= 100$
$1 <= N, M <= 10^5$
$2 <= K <= N$
Length of $s$ will not exceed $10$
For $90 %$ test cases: $1 <= N, M, K <= 1000$
## Input
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.
## Output
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.
[samples]
## Note
$1 <= T <= 100$$1 <= N, M <= 10^5$$2 <= K <= N$Length of $s$ will not exceed $10$For $90 %$ test cases: $1 <= N, M, K <= 1000$
**Definitions**
Let $ n, m \in \mathbb{Z}^+ $ with $ nm $ even.
Let $ G = [n] \times [m] $ be the grid of cells.
Let $ C $ be a partition of $ G $ into $ \frac{nm}{2} $ disjoint pairs of adjacent cells (dominoes), each assigned a unique color.
Let $ \mathcal{P} = \{ (p_i, q_i) \}_{i=1}^{nm/2} $ be the set of domino pairs, where $ p_i, q_i \in G $ are adjacent.
Let $ f: G \to \{1, \dots, \frac{nm}{2}\} $ be the coloring function such that $ f(p) = f(q) $ iff $ (p,q) \in \mathcal{P} $.
Let $ \mathcal{M} \subseteq G \times G $ be the movement graph: $ (u,v) \in \mathcal{M} $ iff $ u $ and $ v $ are adjacent in $ G $ and $ f(u) \ne f(v) $.
**Constraints**
1. $ 1 \le T \le 100 $
2. For each test case:
- $ 1 \le nm \le 10^5 $, $ nm $ even
- $ 1 \le k \le 10^5 $
- Total $ \sum nm \le 2 \times 10^5 $, $ \sum k \le 2 \times 10^5 $
3. For each condition $ j \in \{1, \dots, k\} $:
- Given $ (x_1, y_1), (x_2, y_2) \in G $, and $ c \in \{0,1\} $
- If $ c = 1 $: $ (x_1, y_1) $ and $ (x_2, y_2) $ are in the same connected component of $ \mathcal{M} $
- If $ c = 0 $: $ (x_1, y_1) $ and $ (x_2, y_2) $ are in different connected components of $ \mathcal{M} $
**Objective**
Construct a domino tiling $ \mathcal{P} $ (i.e., a valid coloring $ f $) such that the resulting movement graph $ \mathcal{M} $ satisfies all $ k $ connectivity constraints.
If no such tiling exists, output "No".
Otherwise, output "Yes" and a grid of $ n \times m $ characters, each being $ L, R, U, D $, representing the direction of the domino partner for each cell:
- $ L $: partner is left neighbor
- $ R $: partner is right neighbor
- $ U $: partner is upper neighbor
- $ D $: partner is lower neighbor
(Each cell points to its paired adjacent cell; tiling must be consistent and cover all cells.)