CF2039B Shohag Loves Strings

# Shohag Loves Strings ## 问题描述 给定一个字符串 $s$，定义 $f(p)$ 为字符串 $p$ 的所有不同的非空子字符串的数量。从字符串 $s$ 中找到一个非空子字符串 $p$，使得 $f(p)$ 为偶数。如果找不到这样的子字符串，则输出 $-1$。

- 第一行包含一个整数 $t$，表示测试数量 $(1 \le t \le 10^4)$。 - 接下来 $t$ 行，每行一个字符串 $s$，表示每次测试中的字符串 $s$。$(1 \le |s| \le 10^5)$，且所有字符串的总长度不超过 $3 \times 10^5$。

- 对于每次测试，输出一个非空子字符串 $p$，使得 $f(p)$ 为偶数，如果不存在这样的子字符串，则输出 $-1$ 。若存在多个解，输出任意一个即可。

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.