题目描述

给定一个由小写英文字母组成的字符串 $S$。

请判断是否可以通过重新排列 $S$ 中的字符，使得 任意两个相邻的字符都不相同。如果可以，请找出一种满足条件的重排结果。

给定 $T$ 个测试用例，请分别求解每个用例。

输入格式

T
case_1
case_2
...
case_T

第 $i$ 个 $(1 \le i \le T)$ 测试用例 $\mathrm{case}_i$ 按以下格式给出：

S

输出格式

按顺序输出每个测试用例的答案，用换行分隔。

对于每个测试用例：如果 无法 重排使任意相邻字符都不相同，输出 No。

否则，设 $S'$ 是一种满足条件的重排，按以下格式输出：

Yes
S'

如果存在多个有效的重排方案，输出任意一种均可。

输入示例 1

3
aiiw
doodoo
aabbababcacababaaba

输出示例 1

Yes
iwai
No
Yes
ababacabababacababa

示例 1 说明

考虑第一个测试用例。iwai 是 aiiw 的一种重排，且任意相邻字符都不相同，所以输出 iwai 是正确的。

其他正确的输出包括 wiai、iawi 等。

约束条件

• $1 \le T \le 3 \times 10^5$
• $S$ 是由小写英文字母组成的字符串，$1 \le |S| \le 10^6$
• 所有测试用例中 $|S|$ 的总和不超过 $10^6$