eolymp
bolt
Try our new interface for solving problems
Problems

String merging

String merging

Time limit 1 second
Memory limit 128 MiB

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 data

The first line will contain string A (1 ≤ |A| ≤ 10^5).

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

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

Output data

Print one string C.

Examples

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