#MX176. 字符串还原

字符串还原

时间限制:1000ms

空间限制:512MB

题目描述

给定一个仅由小写字母组成的字符串 tt,它由某个字符串 ss 与其去除所有字符 a 后所得的字符串 s′s' 拼接而成,即 t=s+s′t = s + s'。

请还原原始字符串 ss,或判断无解。

输入格式

第一行一个整数 TT,表示数据组数。

每组数据输入一行,一个字符串,表示 tt。

输出格式

每组数据输出一行,一个字符串,若有解,输出 ss,否则输出 No solution!。

样例 1 输入

2
aabaacbaba
acbaabcbaacbbcb

样例 1 输出

No solution!
acbaabcbaa

样例 2

见下发文件。

数据规模与约定

令 ∣t∣|t| 为 tt​ 的长度。

| 测试点编号 | ∣t∣|t| | 所有 ∣t∣|t| 之和 | | :--------------------------------------: | :----: | :-------------: | | 1,2,3,4,5,61,2,3,4,5,6 | 10310^3 | 10410^4 | | 7,8,9,10,11,12,13,14,15,16,17,18,19,207,8,9,10,11,12,13,14,15,16,17,18,19,20 | 10510^5 | 10610^6 |