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| ≤ 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

Print one string C.

Examples