Smallest palindrome P21831


Statement
 

pdf   zip

thehtml

Implement a program that, for each given word, prints the smallest palindrome (in lexicographical order) that can be formed using exactly all its letters once. The given words as well as the formed palindromes do not necessary have a meaning. If, for any word, is not possible to form any palindrome, it must be indicated.

Input

The input consists of a number k≤ 1000 of words in a line, followed by k lines, each one with a none empty word. The words are exclusively formed by at most 500 lowercase letters.

Your program must solve an input as the described one in less than 1 second.

Output

For each word, your program must print a line with the smallest palindrome that can be formed using exactly once all the letters of the word. If it is not possible to form any palindrome, it must print "NO PALINDROME".

Public test cases
  • Input

    9
    abcabc
    a
    xy
    zzz
    bbaa
    bbbbbccccccaaaa
    aaaabbbccd
    aeeeiiiiiooou
    dabalearrozalazorraelabad
    

    Output

    abccba
    a
    NO PALINDROME
    zzz
    abba
    aabbcccbcccbbaa
    NO PALINDROME
    NO PALINDROME
    aaaabdelorrzlzrroledbaaaa
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Carlos Molina
    Original language
    Spanish
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++