Для строки \(p\) определим \(f(p)\) — количество уникальных непустых подстрок\(^{\text{∗}}\) строки \(p\).
У Shohag есть строка \(s\). Помогите ему найти непустую строку \(p\), такую, что \(p\) является подстрокой \(s\), а \(f(p)\) чётно, или скажите, что такой строки не существует.
Выходные данные
Для каждого набора входных данных выведите непустую строку, удовлетворяющую условиям, или \(-1\), если такой строки не существует. Если существует несколько решений, выведите любое из них.
Примечание
В первом наборе входных данных мы можем выбрать \(p = \) abaa, потому что это подстрока \(s\), а уникальными подстроками \(p\) являются a, b, aa, ab, ba, aba, baa и abaa — всего \(8\) уникальных подстрок, что является чётным числом.
Во втором наборе входных данных мы можем выбрать только \(p = \) a, но у этой строки есть одна уникальная подстрока, что является нечётным числом, поэтому эта строка не подходит.
В третьем наборе входных данных вся строка содержит \(52\) уникальных подстроки, поэтому сама строка является корректным ответом.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
dcabaac
a
youknowwho
codeforces
bangladesh
|
abaa
-1
youknowwho
eforce
bang
|