← 返回题目列表

Codeforces · 2045/C

C. 萨拉加

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

saraga 这个词是 sarana olahraga 的缩写,是印度尼西亚语中体育设施的术语。它是通过采用单词 sarana 的前缀 sara 和单词 olahraga 的后缀 ga 创建的。有趣的是,它也可以由单词 sarana 的前缀 sa 和单词 olahraga 的后缀 raga 创建。

两个字符串 $$$S$$$ 和 $$$T$$$ 的缩写是有趣的,如果至少有两种不同的方法将缩写分成两个非空子字符串,使得第一个子字符串是 $$$S$$$ 的前缀,第二个子字符串是 $$$T$$$ 的后缀。

给你两个字符串 $$$S$$$ 和 $$$T$$$。您想要创建具有最小长度的字符串 $$$S$$$ 和 $$$T$$$ 的有趣缩写,或者确定是否无法创建有趣的缩写。

输入

第一行由字符串 $$$S$$$ ($$$1 \leq |S| \leq 200\,000$$$) 组成。

第二行由字符串 $$$T$$$ ($$$1 \leq |T| \leq 200\,000$$$) 组成。

字符串 $$$S$$$ 和 $$$T$$$ 均仅由小写英文字母组成。

输出

如果无法创建有趣的缩写,则输出 -1。

否则,在单行中输出一个字符串,表示具有最小长度的字符串 $$$S$$$ 和 $$$T$$$ 的有趣缩写。如果有多个解,输出任意一个。

示例

输入 #1

sarana
olahraga

输出 #1

saga

输入 #2

berhiber
wortelhijau

输出 #2

berhijau

输入 #3

icpc
icpc

输出 #3

icpc

输入#4

icpc
jakarta

输出#4

-1

注意

示例输入/输出#1 的说明

您可以将 saga 拆分为 s 和 aga,或 sa 和 ga。缩写 saraga 很有趣,但 saga 的长度较短。

示例输入/输出 #2 的说明

缩写 belhijau 的长度也很有趣,因此它是另一个有效的解决方案。