T2 小朋友

题目信息

时间限制: 1s

空间限制: 512M

输入文件: xiao.in

输出文件: xiao.out

题目描述

有 $N$ 个小朋友在从前到后排队，每个小朋友的衣服的左面和右面各有一个小写拉丁字母（a 到 z 之一）。作为老师，你可以任意选择一些小朋友暂时离队。也可以让所有小朋友都离开或者全都不离开。

小朋友离队之后，所有人从前到后，衣服左面的字母会顺次连接成一个字符串 $S'$，衣服右面的字母会顺次连接成一个字符串 $T'$。两个字符串之后再前后拼接在一起形成 $S'+T'$。

你需要让字符串 $S'+T'$ 的字典序最大。输出可能的字典序最大的 $S'+T'$。

输入格式

输入文件名为 xiao.in。

第一行一个字符串 $S$，从前到后表示小朋友衣服左边的字母；

第二行一个字符串 $T$，从前到后表示小朋友衣服右边的字母；

字母一定是 a 到 z 之一。

两个串的长度相等，为 $N$，表示小朋友个数。

输出格式

输出文件名为 xiao.out。

输出一行一个字符串表示可能的字典序最大的 $S'+T'$。

样例

样例输入 1

ab
zy

样例输出 1

by

样例解释 1

有 $4$ 种可能：空串，az，by，abzy，其中 by 字典序最大。

样例输入 2

abacaba
zzzaaaa

样例输出 2

cbaaaa

样例输入 3

x
x

样例输出 3

xx

样例输入 4

abbabbabbababaaaabbababab
bababbaabbbababbbbababaab

样例输出 4

bbbbbbbbbbbbbbbbbbaaab

数据范围与提示

对于 $100\%$ 的数据，$1\le N\le 50$，输入字符串仅含小写拉丁字母 a 到 z。

• 子任务 $1$（$30$ 分）：$1\le N \le 20$；
• 子任务 $2$（$20$ 分）：$S=T$，小朋友衣服左右字符相同；
• 子任务 $3$（$50$ 分）：无特殊限制；