29508번 - Базовая строка 다국어

Назовем операцией возведения строки $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>>.