← 返回题目列表

Codeforces · 180/D

D. 名称

中文机器翻译题面 查看原题

在遥远的鲸鱼座 Tau 星座,一切都变得模糊起来。具体来说,陶塞派以一种非常奇特的方式为他们的孩子选择名字。

两个年轻的父母 abac 和 bbad 正在考虑给他们的第一个孩子起什么名字。他们决定名称将是字符串 s 的字母的排列。为了跟上邻居的步伐,他们决定给婴儿起名,以便这个名字在字典上严格大于邻居儿子的名字t。

另一方面,他们怀疑很快就会征收姓名税。根据它的说法,字典中名字较大的陶塞蒂亚人将缴纳更多的税。这就是 abac 和 bbad 想要称呼新生儿的原因,以便该名称在字典顺序上严格大于名称 t,并且在字典顺序上最小。

字符串的字典顺序是我们都习惯的顺序,即“字典”顺序。所有现代编程语言都使用这种比较来比较字符串。形式上,如果以下两个陈述之一正确,则长度为 n 的字符串 p 按字典顺序小于长度为 m 的字符串 q:

- n < m,p 是字符串 q 的开头(前缀)(例如,“aba”小于字符串“abaa”),
- p1 = q1, p2 = q2, ..., pk - 1 = qk - 1, pk < qk 对于某些 k (1 ≤ k ≤ min(n, m)),这里字符串中的字符从1.

编写一个程序,给定字符串 s 和邻居孩子的名字 t,确定 s 中字母排列结果的字符串。该字符串按字典顺序应严格大于 t,并且按字典顺序最小。

输入

第一行包含一个非空字符串 s (1 ≤ |s| ≤ 5000),其中 |s|是它的长度。第二行包含一个非空字符串 t (1 ≤ |t| ≤ 5000),其中 |t|是它的长度。两个字符串均由小写拉丁字母组成。

输出

打印所查找的名称,如果不存在则打印 -1。

示例

输入 #1

aad
aac

输出 #1

aad

输入 #2

abad
bob

输出 #2

daab

输入 #3

abc
defg

输出 #3

-1

输入#4

czaaab
abcdef

输出#4

abczaa

注意

在第一个示例中,给定的字符串 s 是要查找的字符串,因此,我们不需要更改那里的字母顺序。