|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||256 MB||28||14||14||66.667%|
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:
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