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 AA of length NN and BB of length MM. You are supposed to take a prefix PAP_A of any length (maybe 0) from AA and a suffix SBS_B of any length (maybe 0) from BB. After concatenating PAP_A and SBS_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 AA and the second line contains string BB (2N+M2106)(2 \leq N + M \leq 2\cdot10^{6}).
AA and BB 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


70% Solution Ratio

serotoninEarliest, Jul '20

Zobayer_AbedinFastest, 0.0s

imdumbLightest, 6.2 MB

Zobayer_AbedinShortest, 935B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.