题解

题面描述

给定两个数列

• 数列$s_1$由若干个非负整数（每个数字范围为$0\sim9$，注意$s_1$可能包含$0$）构成，
• 数列$s_2$同样由非负整数组成。

可以对数列$s_1$进行任意次操作，每次操作可交换其中任意两个数字的位置，也就是说可以任意排列数列$s_1$中的数字。目标是让排列后的$s_1$构成的数字最大，但同时必须严格小于数列$s_2$构成的数字。如果不存在满足条件的排列，则输出$-1$。

题目内容

多多有两个仅由正整数构成的数列$s_1$和$s_2$,多多可以对$s_1$进行任意次操作,每次操作可以置换$s_1$中任意两个数字的位置.

多多想让数列$s_1$构成的数字尽可能大,但是小于$s_2$

请问再经过任意次操作后,满足上述条件的数列$s_1$构成的数字是多少.

输入描述

第一行,包含一个正整数$T(1≤T≤10)$代表测试数据的组数.

对于每组测试数据,分别有三行:

第一行,有两个正整数$n(1≤n≤10^5)$, $m(1≤m≤10^5)$,分别表示数列$s_1$和$s_2$的长度.

第二行,有一行仅由正整数组成的的长度为$n$数列$s_1$

第三行，有一行仅由正整数组成的的长度为$m$数列$s_2$

输出描述

对于每组数据,输出数列$s_1$在经过任意次置换操作后,得到的满足条件的最大值数字

如果不存在这样的数字,则输出$-1$

样例1

输入

3
5 5
12345
45678
5 5
65479
54231
5 5
42315
12345

输出

45321
49765
-1