帕秋莉掌握了一种水属性魔法
这种魔法可以净化黑暗
帕秋莉发现对于一个黑暗的咒语s，可以使用这个水元素魔法净化它，净化的咒语是一个最长的字符串t，t满足以下条件：
它是s的前缀
它是s的后缀
除前缀和后缀外，它还在s中出现过至少一次
既然你都学会了，那么净化的工作就交给你了！
一行字符串 s ，代表黑暗咒语
一个字符串 t ，表示满足条件的最长净化咒语
tqrwantoacthisproblembutqristooweaktodoitqr
tqr
对于60%的数据，s长度≤100对于100%的数据，s长度≤100,000保证存在可行的净化咒语