Shohag Loves Strings
Contest: CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 1000
Tags: constructive algorithms, greedy, implementation, strings

For a string $$$p$$$, let $$$f(p)$$$ be the number of distinct non-empty substrings$$$^{\text{∗}}$$$ of $$$p$$$.

Shohag has a string $$$s$$$. Help him find a non-empty string $$$p$$$ such that $$$p$$$ is a substring of $$$s$$$ and $$$f(p)$$$ is even or state that no such string exists.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first and only line of each test case contains a string $$$s$$$ ($$$1 \le |s| \le 10^5$$$) consisting of lowercase English letters.

It is guaranteed that the sum of the length of $$$s$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case, print a non-empty string that satisfies the conditions mentioned in the statement, or $$$-1$$$ if no such string exists. If there are multiple solutions, output any.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, we can set $$$p = $$$ abaa because it is a substring of $$$s$$$ and the distinct non-empty substrings of $$$p$$$ are a, b, aa, ab, ba, aba, baa and abaa, so it has a total of $$$8$$$ distinct substrings which is even.

In the second test case, we can only set $$$p = $$$ a but it has one distinct non-empty substring but this number is odd, so not valid.

In the third test case, the whole string contains $$$52$$$ distinct non-empty substrings, so the string itself is a valid solution.

Example input:
5
dcabaac
a
youknowwho
codeforces
bangladesh

Example output:
abaa
-1
youknowwho
eforce
bang

Editorial:
THOUGHT: The condition seems hard to track. So a good way is to play around with smaller cases and see if we can make some observations.
ACTION: Let's start with the smallest string. When $$$s=$$$ a, the number of unique substrings $$$f(s) = 1$$$, so it's odd and not valid.
OBSERVATION: No one length strings are valid.
ACTION: Let's try the next smallest strings.
When $$$s=$$$ aa, $$$f(s) = 2$$$, so it's even and valid.
When $$$s=$$$ ab, $$$f(s) = 3$$$, so it's odd and not valid.
OBSERVATION: Two length strings are valid if the adjacent characters are same.
THOUGHT: So if $$$s$$$ contains two consecutive same characters, we can print it right away. All that remains is to consider strings without two consecutive same characters.
ACTION: Let's try the next smallest strings with adjacent different characters.
When $$$s=$$$ aba, $$$f(s) = 5$$$, so it's odd and not valid.
When $$$s=$$$ abc, $$$f(s) = 6$$$, so it's even and valid.
OBSERVATION: Three length strings are valid if all characters are different.
THOUGHT: So if $$$s$$$ contains three consecutive different characters, we can print it right away.
All that remains is to consider strings without two adjacent same characters but no three consecutive different characters.
So all the remaining strings are of the form $$$s =$$$ abababababa...
Let's try to see if we can make some observations about these strings.
ACTION: Let's try to calculate the number of unique substrings for a string of the form $$$s =$$$ abababababa...
• There are exactly $$$2$$$ unique substrings of length $$$1$$$: a and b.
• There are exactly $$$2$$$ unique substrings of length $$$2$$$: ab and ba.
• There are exactly $$$2$$$ unique substrings of length $$$3$$$: aba and bab.
• $$$\ldots$$$
• There are exactly $$$2$$$ unique substrings of length $$$n - 1$$$.
• However, the length $$$n$$$ substring occurs exactly once.
OBSERVATION: The number of unique substrings of any length is $$$2$$$. But only the length $$$n$$$ substring occurs exactly once. So total number of unique substrings is $$$2n - 1$$$. And this is always odd! So there is no solution for these strings.
THOUGHT: We have covered all the cases.
CONCLUSION: If there are adjacent same characters, we can print it right away. If there are three consecutive different characters, we can print it right away. Otherwise there is no solution.
Time Complexity: $$$\mathcal{O}(n)$$$.