E. Сжать строку

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

Считается то же самое: $d = n - p_{n-1}$. Если $n$ делится на $d$, ответ — префикс длины $d$. Иначе строка не сжимается, и ответ — она сама.

Стоит проговорить, почему наименьший период даёт именно наименьшее $t$: любое разложение $s = t^k$ означает, что $|t|$ — период строки и делитель $n$, а наименьший период — наименьший из таких.

Обратите внимание, что не всякий период годится в качестве длины $t$: нужен делитель. Например, у aabaaa наименьший период равен 4, но $6$ на $4$ не делится, и строка не сжимается.

Одна строка длины $n$ ($1 \le n \le 10^6$) из строчных латинских букв.

Одна строка — наименьшая $t$, для которой $s$ является её повторением.