eolymp
Competitions

2019 Fall KBTU OPEN

String merging

In this problem you will be given two strings A and B.

Your task is to find a string C such that it contains both A and B as substring and it will be shortest among all possible strings.

A substring of a string is a contiguous subsequence of that string. So, string kbtu is substring of string kbtu open, but string fall is not.

Input

The first line will contain string A (1 ≤ |A| ≤ 105).

The second line of the input will contains string B (1 ≤ |B| ≤ 105).

It is guaranteed that both strings will contain only lowercase Latin letters.

Output

Print one string C.

Time limit 1 second
Memory limit 128 MiB
Input example #1
compressing
single
Output example #1
compressingle
Input example #2
can
you
Output example #2
youcan
Input example #3
compressiondoneright
doner
Output example #3
compressiondoneright
Source 2019 Fall KBTU OPEN, Problem A