Least Common Divisor

Interview

Time limit2sMemory limit512 MB

Summary

Given two short strings, find the shortest string that divides both, meaning it repeats a whole number of times to form each, or report that none exists.

Level: Medium4 of 10
Topics: String, Math, Number theory, Brute force
Solved: No attempts yet

Problem

A divisor of string $A$ is a string $D$ that can be repeated an integer number of times to obtain $A$ . For example, the divisors of the string "aaaa" are "a", "aa", and "aaaa", and the divisors of the string "ababab" are "ab" and "ababab".

Given two strings $S$ and $T$ , find the shortest string that is both a divisor of $S$ and a divisor of $T$ , or determine that no such string exists.

Input

The first line contains the string $S$ , and the second line contains the string $T$ . Each string has length between 1 and 50 characters, inclusive, and consists only of lowercase English letters.

Output

Print the least common divisor of the strings $S$ and $T$ , or the string "No solution" if the least common divisor does not exist.

Examples3

Example 1
Input
```
abab
ababab
```
Expected output
```
ab
```
Example 2
Input
```
aaaa
aaaa
```
Expected output
```
a
```
Example 3
Input
```
abc
de
```
Expected output
```
No solution
```