库兹涅科夫喜欢艺术、诗歌和音乐。以及由小写英文字母组成的字符串。
最近,Kuznecov 发现了两个字符串 $$$a$$$ 和 $$$b$$$,长度分别为 $$$n$$$ 和 $$$m$$$。它们由小写英文字母组成,并且两个字符串中都不包含任何字符。
让另一个字符串 $$$c$$$ 最初为空。库兹涅科夫可以执行以下两种类型的操作:
- 从字符串 $$$a$$$ 中选择任意字符,将其从 $$$a$$$ 中删除,并将其添加到 $$$c$$$ 的末尾。
- 从字符串 $$$b$$$ 中选择任意字符,将其从 $$$b$$$ 中删除,并将其添加到 $$$c$$$ 的末尾。
但是,他不能连续执行超过 $$$k$$$ 相同类型的操作。他必须执行操作,直到 $$$a$$$ 或 $$$b$$$ 变空。他完成后 $$$c$$$ 的字典顺序最小可能值是多少?
当且仅当满足以下条件之一时,字符串 $$$x$$$ 按字典顺序小于字符串 $$$y$$$:
- $$$x$$$ 是 $$$y$$$ 的前缀,但 $$$x \neq 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$$$ — 问题的答案。
示例
输入 #1
3 6 4 2 aaaaaa bbbb 5 9 3 caaca bedededeb 7 7 1 noskill wxhtzdy
输出 #1
aabaabaa aaabbcc dihktlwlxnyoz
注意
在第一个测试用例中,最好从字符串 $$$a$$$ 中取出两个“a”并将它们添加到字符串 $$$c$$$ 中。那么就禁止从 $$$a$$$ 中取出更多字符,因此必须从字符串 $$$b$$$ 中取出一个字符“b”。按照这个逻辑,当字符串 $$$a$$$ 被清空时,我们最终会得到 $$$c$$$ 为 'aabaabaa' 的结果。
在第二个测试用例中,最佳做法是从字符串 $$$a$$$ 中取出尽可能多的 'a',然后从字符串 $$$b$$$ 中取出尽可能多的 'b'。最后,我们从字符串 $$$a$$$ 中取出两个 'c' 将其清空。