시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 17 5 5 50.000%

문제

Somewhere on the outskirts of Leiden’s music scene, there is an obscure instrumental rock group consisting of students from Leiden University. They call themselves naaagrm, which is an anagram of an existing word in the Swedish language. All of their song titles are anagrams of existings words as well. However, many people seem to struggle with the pronunciation of the band name, as they don’t know how to properly pronunciate the triple a (in case you were wondering, it is pronounced as what linguists like to call an open front unrounded vowel, and a very long one at that). Therefore the band members have decided to modify all their song titles by changing the order of the letters in such a way that no two consecutive letters are the same. Since this is a tedious task, they ask for your help.

입력

The input starts with a line containing an integer T, the number of test cases. Then for each test case:

  • One line containing a single string, the current name of the song. The string consists of lowercase letters only, and has length between 1 and 105 inclusive.

출력

For each test case, output an anagram of the input string such that no two consecutive letters are the same. If there are multiple ways to do this, output the lexicographically smallest one. If it is impossible to do so, output IMPOSSIBLE instead.

예제 입력

5
naaagrm
hiking
snaaan
banana
aaaaaaargh

예제 출력

agamanr
ghikin
ananas
abanan
IMPOSSIBLE

힌트