Batman Needs Your Help!

Hello Batman or Joker fans!! You all know that in the history of movie, one of the smartest villain is Joker. The reason behind of it is Joker always gives brainstorming challenges to the Gotham police as well as Batman.

This time Joker locked up Batman. He gave a string related challenge to Gordon(chief of Gotham police) and asked to find a new string from two original strings. This new string is the password to rescue Batman. Gordon came to you to solve this challenge.

Joker gave two non-empty strings $A$ of length $N$ and $B$ of length $M$. You are supposed to take a prefix $P_A$ of any length (maybe 0) from $A$ and a suffix $S_B$ of any length (maybe 0) from $B$. After concatenating $P_A$ and $S_B$, the new resulting string need to be palindrome. And the length of the determined string should be maximum. If multiple string of same length can be determined then choose lexicographically minimum.

Dare you to take this challenge and rescue Batman?

Input

The first line contains string $A$ and the second line contains string $B$ $(2 \leq N + M \leq 2\cdot10^{6})$.
$A$ and $B$ consist of lowercase Latin alphabet.

Output

Print the determined string in a single line.

Samples

Input	Output
abcded cbaa	aaa

Input	Output
abcded cba	abcdedcba