Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Batman Needs Your Help!

By al.noman · Limits 1s, 512 MB

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

InputOutput
abcded
cbaa
aaa
InputOutput
abcded
cba
abcdedcba

    Discussion

    Statistics


    72% Solution Ratio

    serotoninEarliest, 2w ago

    MatrixFastest, 0.0s

    imdumbLightest, 6.2 MB

    serotoninShortest, 1222B

    Submit

    Login to submit