Content:
简体中文
你聽過回文樹嗎?這是⼀種可以在 O(N|Σ|) 的時間內算出一個長度為 N 的字串 S 的所有回文子字串出現次數的資料結構,其中 |Σ| 為字元集的大小。例如,當 S 是 abacaba 時,子字串 a 、b 、aba 、aca 、bacab 、abacaba 皆是回文,且其中 aba 出現了兩次、a 出現了四次。
由於回文樹不僅功能強大,種在路邊作為行道樹也可以美化市容。更重要的是,如果用回文來灌溉它的話,它就會將城市中的廢氣轉為清新的空氣!長年受到空氣污染影響的 NPSC 國當然不會放過這個機會,因此 NPSC 國政府從回文樹的原⽣地 CSPN 國購進了大量的回文樹,並打算用大量的回文來灌溉它。
不過,NPSC 國很快就發現了,如果灌溉用的回文的字典序不夠小的話,可能反而造成反效果,使得回文樹枯萎而死。因此,政府打算重新排列手上的字串,使得它變成回文且字典序最小。請幫助 NPSC 國找到字典序最小的回文,解決空汙的問題!
Input:
輸入第一行有一個正整數 T ,代表回文樹的肥料個數。接著 T 行,每行有⼀個非空字串 S,代表⼀個灌溉用的字串。
Output:
Sample Input:
2 ACCBBA ABC
Sample Output :
ABCCBA NPSCCSPN
Hint
:
Author
: