시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 512 MB76583.333%

문제

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

Consider two strings $S$ and $T$. Find the shortest of strings which are simultaneously divisors of $S$ and divisors of $T$, or determine that there are no such strings.

입력

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

출력

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

예제 입력 1

abab
ababab

예제 출력 1

ab

예제 입력 2

aaaa
aaaa

예제 출력 2

a

예제 입력 3

abc
de

예제 출력 3

No solution