B Letters Rearranging

2018-12-16 19:27:16


题目链接:

https://codeforces.com/contest/1093/problem/B

原题:

Problem Statement

You are given a string s consisting only of lowercase Latin letters.

You can rearrange all letters of this string as you wish. Your task is to obtain a good string by rearranging the letters of the given string or report that it is impossible to do it.

Let's call a string good if it is not a palindrome. Palindrome is a string which is read from left to right the same as from right to left. For example, strings "abacaba", "aa" and "z" are palindromes and strings "bba", "xd" are not.

You have to answer t independent queries.

Input

The first line of the input contains one integer t (1≤t≤100) — number of queries.

Each of the next t lines contains one string. The i-th line contains a string si consisting only of lowercase Latin letter. It is guaranteed that the length of si is from 1 to 1000 (inclusive).

Output

Print t lines. In the i-th line print the answer to the i-th query: -1 if it is impossible to obtain a good string by rearranging the letters of si and any good string which can be obtained from the given one (by rearranging the letters) otherwise.

Examples

input

3
aa
abacaba
xdd

output

-1
abaacba
xdd

Note

In the first query we cannot rearrange letters to obtain a good string.

Other examples (not all) of correct answers to the second query: "ababaca", "abcabaa", "baacaba".

In the third query we can do nothing to obtain a good string.


题意:

把一个回文变成一个非回文,若输入的本来就是非回文,就原样输出,若变不成非回文,就输出-1

思路:

三种情况:

1.回文,变不成非回文——>-1

2.回文,能变成非回文——>非回文

3.非回文——>原样输出

AC代码:

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
#include<algorithm>
#include<queue>
typedef long long ll;
#include<vector>
#define cin(n) scanf("%lld",&(n))
#define cout(n) printf("%lld",(n))
#define couc(c) printf("%c",(c))
#define coutn printf("\n")
#define cout_ printf(" ")
#define debug() printf("haha\n")
const int MAXN= 1e6 + 5 ;
ll t;
ll n,k;
ll a[1005];
ll ans;
char s[1005];
int main()
{
    cin(t);
    for(int i=1;i<=t;i++)
    {
        scanf("%s",s);
        int len=strlen(s);
        memset(a,0,sizeof(a));
        int ans=0;
        int flag=0;
        for(int i=0;i<len/2;i++)
        {
            if(s[i]!=s[len-i-1])
            {
                printf("%s\n",s);
                flag=1;
                break;
            }
            if(a[s[i]]==0)
            {
                ans++;
            }
            a[s[i]]++;
            if(a[s[len-i-1]]==0)
            {
                ans++;
            }
            a[s[len-i-1]]++;
        }
        if(len%2)
        {
            if(a[s[len/2]]==0)
            {
                ans++;
            }
            a[s[len/2]]++;

        }

        if(flag)
            continue;
        if(ans==1)
            printf("-1\n");
        else
        {
            for(int i=1;i<1005;i++)
                while(a[i])
                {
                    printf("%c",i);
                    a[i]--;
                }
            coutn;
        }
    }
    return 0;
}