Строка \(s\) длины \(n\) может быть зашифрована следующим алгоритмом:
- переберём все делители числа \(n\) в порядке убывания (то есть от \(n\) до \(1\)),
- для каждого делителя \(d\) перевернём подстроку \(s[1 \dots d]\) (то есть такую подстроку, которая начинается в позиции \(1\) и заканчивается в позиции \(d\)).
Например, если алгоритм применяется к строке \(s\)=«codeforces», то строка будет изменяться следующим образом: «codeforces» \(\to\) «secrofedoс» \(\to\) «orcesfedoс» \(\to\) «rocesfedoс» \(\to\) «rocesfedoс» (очевидно, последний переворот не изменяет строку, так как \(d=1\)).
Вам дана зашифрованная строка \(t\). Требуется произвести расшифровку, то есть найти такую строку \(s\), в результате шифровки которой получится строка \(t\). Можно доказать, что такая строка \(s\) всегда существует (и при этом единственная).
Выходные данные
Выведите такую строку \(s\), что если зашифровать ее описанным выше алгоритмом, то получится строка \(t\).
Примечание
Первый пример разобран в условии задачи.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
10
rocesfedoc
|
codeforces
|
|
2
|
16
plmaetwoxesisiht
|
thisisexampletwo
|
|
3
|
1
z
|
z
|