Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 1865
Suffidromes

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Given two strings of lowercase letters, a and b, print the shortest string x of lowercase letters such that exactly one (but not both) of ax or bx is a palindrome; that is, equal to itself when reversed.


Input

Standard input contains several pairs of a and b. Each string is on a separate line and consists of between 0 and 1,000 lowercase letters.


Output

For each pair, output a line containing x. If several x satisfy the criteria above, choose the first one in alphabetical order.

Print a line "No Solution." if there does not exist such x.


Sample Input

abab
ababab
abc
def


Sample Output

baba
ba


Source: University of Waterloo Local Contest 1999.10.02
Submit    Status