题目描述

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

最近，Kuznecov 找到了两个字符串 $a$ 和 $b$，它们的长度分别为 $n$ 和 $m$。这两个字符串只包含小写英文字母，并且没有任何字符同时出现在 $a$ 和 $b$ 中。

现在有一个初始为空的字符串 $c$。Kuznecov 可以进行以下两种操作：

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

但是，他不能连续进行超过 $k$ 次同一种类型的操作。他必须一直进行操作，直到 $a$ 或 $b$ 变为空为止。请问操作结束后，字符串 $c$ 的字典序最小可能值是多少？

如果字符串 $x$ 是字符串 $y$ 的前缀且 $x \neq y$，则 $x$ 的字典序小于 $y$。或者，在 $x$ 和 $y$ 第一个不同的位置，$x$ 的字母比 $y$ 的对应字母在字母表中更靠前，则 $x$ 的字典序小于 $y$。

输入格式

输入包含若干组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 100$），表示测试用例的数量。接下来是每组测试数据的描述。

每组测试数据的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \leq n, m, k \leq 100$）。

第二行包含长度为 $n$ 的字符串 $a$。

第三行包含长度为 $m$ 的字符串 $b$。

字符串只包含小写英文字母，并且保证 $a$ 和 $b$ 没有公共字符。

输出格式

对于每组测试数据，输出一个字符串 $c$，即问题的答案。

说明/提示

在第一个测试用例中，最优的做法是先从字符串 $a$ 中取出两个 'a' 并加入字符串 $c$。此时不能再连续从 $a$ 取字符，因此必须从 $b$ 中取一个 'b'。按照这个逻辑，最终当 $a$ 被取空时，$c$ 为 'aabaabaa'。

在第二个测试用例中，最优的做法是尽可能多地从 $a$ 中取 'a'，然后尽可能多地从 $b$ 中取 'b'。最后再取两个 'c' 使 $a$ 取空。

由 ChatGPT 4.1 翻译

样例

3
6 4 2
aaaaaa
bbbb
5 9 3
caaca
bedededeb
7 7 1
noskill
wxhtzdy

aabaabaa
aaabbcc
dihktlwlxnyoz