#P. JIXMPII57IFY100#*':

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l m n

传统题

2000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Statement

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.

$^{\text{∗}}$ A string $a$ is a substring of a string $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.

Format

Input

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

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.

Sample

5
dcabaac
a
youknowwho
codeforces
bangladesh

abaa
-1
youknowwho
eforce
bang

ShanghaiTech ACM 炸鱼杯

未参加

状态: 已结束
规则: OI
题目: 46
开始于: 2024-12-10 23:00
结束于: 2024-12-15 13:00
持续时间: 110 小时
主持人: _Arahc_
参赛人数: 112

#P. JIXMPII57IFY100#*':

JIXMPII57IFY100#*':

Statement

Format

Input

Output

Sample

ShanghaiTech ACM 炸鱼杯

状态

开发

支持

#P. JIXMPII57IFY100#*':

JIXMPII57IFY100#*':

Statement

Format

Input

Output

Sample

ShanghaiTech ACM 炸鱼杯

状态

开发

支持

还没有账户？

登录