CF1689A.Lex String

Kuznecov likes art, poetry, and music. And strings consisting of lowercase English letters.

Recently, Kuznecov has found two strings, $a$ and $b$, of lengths $n$ and $m$ respectively. They consist of lowercase English letters and no character is contained in both strings.

Let another string $c$ be initially empty. Kuznecov can do the following two types of operations:

• Choose any character from the string $a$, remove it from $a$, and add it to the end of $c$.
• Choose any character from the string $b$, remove it from $b$, and add it to the end of $c$.

But, he can not do more than $k$ operations of the same type in a row. He must perform operations until either $a$ or $b$ becomes empty. What is the lexicographically smallest possible value of $c$ after he finishes?

A string $x$ is lexicographically smaller than a string $y$ if and only if one of the following holds:

• $x$ is a prefix of $y$, but $x \neq y$;
• in the first position where $x$ and $y$ differ, the string $x$ has a letter that appears earlier in the alphabet than the corresponding letter in $y$.

库兹涅佐夫喜欢艺术、诗歌和音乐，也喜欢由小写英文字母组成的字符串。

最近，库兹涅佐夫找到了两个字符串 $a$ 和 $b$，长度分别为 $n$ 和 $m$。它们均由小写英文字母组成，且两个字符串中不包含任何相同的字符。

另设一个字符串 $c$ 初始为空。库兹涅佐夫可以执行以下两种操作：

• 从字符串 $a$ 中任选一个字符，将其从 $a$ 中删除，并添加到 $c$ 的末尾；
• 从字符串 $b$ 中任选一个字符，将其从 $b$ 中删除，并添加到 $c$ 的末尾。

但他在连续操作中，同一种操作最多只能执行 $k$ 次。他必须持续执行操作，直到 $a$ 或 $b$ 中至少有一个变为空。那么，当操作结束时，$c$ 可能取得的字典序最小值是多少？

字符串 $x$ 的字典序小于字符串 $y$，当且仅当满足以下条件之一：

• $x$ 是 $y$ 的真前缀（即 $x$ 是 $y$ 的前缀，但 $x \neq y$）；
• 在 $x$ 与 $y$ 首次出现不同字符的位置上，$x$ 中该位置的字母在字母表中早于 $y$ 中对应位置的字母。

There are several test cases in the input data. The first line contains a single integer $t$ ($1 \leq t \leq 100$) — the number of test cases. This is followed by the test cases description.

The first line of each test case contains three integers $n$, $m$, and $k$ ($1\leq n,m,k \leq 100$) — parameters from the statement.

The second line of each test case contains the string $a$ of length $n$.

The third line of each test case contains the string $b$ of length $m$.

The strings contain only lowercase English letters. It is guaranteed that no symbol appears in $a$ and $b$ simultaneously.

输入数据包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 100$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$m$ 和 $k$（$1\leq n,m,k \leq 100$），即题目中给出的参数。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $a$。

每个测试用例的第三行包含一个长度为 $m$ 的字符串 $b$。

字符串仅由小写英文字母组成。保证没有任何字符同时出现在 $a$ 和 $b$ 中。

In each test case, output a single string $c$ — the answer to the problem.

在每个测试用例中，输出一个字符串 $c$ —— 该问题的答案。

In the first test case, it is optimal to take two 'a's from the string $a$ and add them to the string $c$. Then it is forbidden to take more characters from $a$, hence one character 'b' from the string $b$ has to be taken. Following that logic, we end up with $c$ being 'aabaabaa' when string $a$ is emptied.

In the second test case it is optimal to take as many 'a's from string $a$ as possible, then take as many 'b's as possible from string $b$. In the end, we take two 'c's from the string $a$ emptying it.

在第一个测试用例中，最优策略是从字符串 $a$ 中取两个字符 'a' 并添加到字符串 $c$ 中。此后，禁止再从 $a$ 中取字符，因此必须从字符串 $b$ 中取一个字符 'b'。依此逻辑，当字符串 $a$ 被取空时，最终 $c$ 变为 'aabaabaa'。

在第二个测试用例中，最优策略是尽可能多地从字符串 $a$ 中取字符 'a'，然后尽可能多地从字符串 $b$ 中取字符 'b'。最后，从字符串 $a$ 中取两个字符 'c'，从而将其取空。