Lex String

题意翻译

给定两个字符串 $a,b$，保证两个字符串中的字符无交，即不存在某个字符同时在两个串中都出现了，要求通过以下的两种操作构造一个新的字符串 $c$，使得 $c$ 的字典序最小，并且要求不能连续使用某一种操作超过 $k$ 次。 1.从 $a$ 中**任选**一个字符插入到 $c$ 的末尾。 2.从 $b$ 中**任选**一个字符插入到 $c$ 的末尾。 若某一个字符串为空则认为构造结束。 若字符串 $x$ 比字符串 $y$ 字典序小则必定满足**以下两种情况**之一： 1.$x$ 为 $y$ 的前缀，且 $x \not= y$。 2.从左到右的顺序，$x$ 与 $y$ 第一个不同的位置上 $x$ 的字符的字典序比 $y$ 的字符的字典序小。 ----$By$ linyihdfj

题目描述

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 $ .

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

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

输出样例 #1

aabaabaa
aaabbcc
dihktlwlxnyoz

说明

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.