문자열 연결

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

요약

소문자로 이루어진 두 문자열 r과 s를 입력받아 r^m과 s^n이 같아지는 가장 작은 m과 n을 구하거나, 없으면 NAO를 출력합니다.

문제

문자열 $s$ 에 대해 $s$ 를 $n$ 번 이어 붙인 문자열을 $s^n$ 으로 나타낸다. 예를 들어 $s$ = "eri", $n$ = 3이면 $s^3$ = "erierieri"이다.

주어진 문자열 $r$ 과 $s$ 에 대해 $r^m = s^n$ 을 만족하는 정수 $m$ 과 $n$ 이 존재하는지 판별한다.

입력의 각 줄에는 공백으로 구분된 두 문자열이 주어진다. 각 문자열은 소문자로만 이루어져 있으며, 길이는 1 이상 1,000,000 이하이다.

입력의 마지막 줄은 공백으로 구분된 두 개의 "#"이다. 이 줄은 처리하지 않는다.

입력의 각 줄마다 한 줄을 출력한다. 조건을 만족하는 정수가 존재하면 가장 작은 정수 $m$ 과 $n$ 을 공백으로 구분하여 출력한다. 존재하지 않으면 "NAO"를 출력한다.

예제 1

입력

aa aaa
abra cadabra
abcabcabcabcabcabc abcabcabcabc
rai mano
# #

예상 출력

3 2
NAO
2 3
NAO