시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB55191944.186%

문제

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.

예제 입력 1

5
naaagrm
hiking
snaaan
banana
aaaaaaargh

예제 출력 1

agamanr
ghikin
ananas
abanan
IMPOSSIBLE

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2015 Preliminaries J번

  • 문제를 만든 사람: Josse van Dobben de Bruyn