Tail Palindrome

Time limit1sMemory limit128 MB

Summary

Given two lowercase strings a and b, find the shortest string x such that exactly one of ax, bx is a palindrome, and among ties the lexicographically smallest x.

Level: Hard8 of 10
Topics: String, String matching, Greedy, Brute force
Solved: No attempts yet

Problem

You are given two strings a and b consisting of lowercase English letters. You want to append a string x so that ax or bx becomes a palindrome (a string that reads the same forwards and backwards). However, ax and bx must not both be palindromes at the same time; that is, exactly one of ax and bx must be a palindrome. Find the shortest string x that satisfies this condition.

Input

The input consists of several test cases. Each test case has two lines: the first line contains the string a and the second line contains the string b. Each string consists of 0 to 1,000 lowercase English letters. The input continues until end of file (EOF).

Output

For each test case, print on its own line the shortest string x that satisfies the condition. If several shortest strings x exist, print the lexicographically smallest one. If x is the empty string, print an empty line. If no such x exists, print "No Solution."

Examples3

Example 1
Input
```
abab
ababab
abc
def
```
Expected output
```
baba
ba
```
Example 2
Input
```
aba
aba
```
Expected output
```
No Solution.
```
Example 3
Input
```
abcba
abcbc
```
Expected output