← 返回题目列表

Codeforces · 1504/A

A. 似曾相识

中文机器翻译题面 查看原题

回文是向后读与向前读相同的字符串。例如,字符串“z”、“aaa”、“aba”和“abccba”是回文,但“codeforces”和“ab”不是回文。你讨厌回文,因为它们给你似曾相识的感觉。

有一个字符串$$$s$$$。您必须在 $$$s$$$ 中的某处插入一个字符“a”。如果可以创建一个不是回文的字符串,您应该找到一个示例。否则,你应该报告这是不可能的。

例如,假设 $$$s=$$$ "cbabc"。通过插入“a”,您可以创建“acbabc”、“cababc”、“cbaabc”、“cbabac”或“cbabca”。然而“cbaabc”是一个回文,因此您必须输出其他选项之一。

输入

第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。

每个测试用例中唯一的一行包含一个由小写英文字母组成的字符串$$$s$$$。

所有字符串的总长度不超过$$$3\cdot 10^5$$$。

输出

对于每个测试用例,如果没有解决方案,则输出“NO”。

否则,在下一行输出“YES”,后跟您构造的长度为 $$$|s|+1$$$ 的字符串。如果有多个解决方案,您可以打印任何一个。

您可以以任何大小写(大写或小写)打印“YES”和“NO”的每个字母。

示例

输入 #1

6
cbabc
ab
zza
ba
a
nutforajaroftuna

输出 #1

YES
cbabac
YES
aab
YES
zaza
YES
baa
NO
YES
nutforajarofatuna

注意

语句中描述了第一个测试用例。

在第二个测试用例中,我们可以制作“aab”或“aba”。但“aba”是回文,因此“aab”是唯一正确的答案。

在第三个测试用例中,“zaza”和“zzaa”是正确答案,但“azza”不是。

在第四个测试用例中,“baa”是唯一正确的答案。

在第五个测试用例中,我们只能制作“aa”,这是一个回文。所以答案是“不”。

在第六个测试用例中,“anutforajaroftuna”是回文,但在其他地方插入“a”是有效的。