Давайте определим операцию умножения между строкой \(a\) и положительным целым числом \(x\): \(a \cdot x\) — это строка, которая является результатом записи \(x\) копий \(a\) одна за другой. Например, «abc» \(\cdot~2~=\) «abcabc», «a» \(\cdot~5~=\) «aaaaa».
Строка \(a\) делится на другую строку \(b\), если существует целое число \(x\) такое, что \(b \cdot x = a\). Например, «abababab» делится на «ab», но не делится на «ababab» или «aa».
LCM из двух строк \(s\) и \(t\) (определяется как \(LCM(s, t)\)) — это самая короткая непустая строка, которая делится как на \(s\), так и на \(t\).
Вам даны две строки \(s\) и \(t\). Найдите \(LCM(s, t)\) или сообщите, что он не существует. Можно показать, что если \(LCM(s, t)\) существует, то он единственный.
Выходные данные
Для каждого набора входных данных выведите \(LCM(s, t)\), если он существует; в противном случае выведите -1. Можно показать, что если \(LCM(s, t)\) существует, то он единственный.
Примечание
В первом примере «baba» = «baba» \(\cdot~1~=\) «ba» \(\cdot~2\).
Во втором примере, «aaaaaa» = «aa» \(\cdot~3~=\) «aaa» \(\cdot~2\).