Базовая строка

시간 제한2초메모리 제한1024 MB

요약

문자열 s와 t가 모두 q의 정수 거듭제곱이 되는 가장 긴 q를 구하거나, 존재하지 않으면 NO를 출력한다.

난이도: 보통10점 중 6점
유형: 문자열, 문자열 매칭, 정수론
정답자: 아직 제출이 없습니다

문제

Назовем операцией возведения строки $s$ в целую степень $n$ повторение этой строки $n$ раз. Результат этой операции будем обозначать $t^n$ . Например, при возведении строки $abac$ в квадрат получается строка $abacabac = (abac)^2$ .

Базовой строкой двух строк $s$ и $t$ назовем максимальную по длине строку $q$ такую, что $s = q^i$ и $t = q^j$ для некоторых натуральных чисел $i$ и $j$ .

Ваша задача состоит в том, чтобы по заданным строкам $s$ и $t$ найти их базовую строку или определить, что такой не существует.

입력

Первая строка входного файла содержит строку $s$ , вторая содержит строку $t$ .

Обе строки непустые и имеют длину не более $10^6$ символов и состоят только из строчных латинских букв.

출력

В выходной файл выведите требуюмую базовую строку $q$ , если же такой не существует, выведите <<NO>>.

예제2

예제 1
입력
```
aaa
aa
```
예상 출력
```
a
```
예제 2
입력
```
a
b
```
예상 출력
```
NO
```