← 返回题目列表

Codeforces · 1379/A

A. 金合欢和弦

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

Acacius 正在研究弦理论。今天他遇到了以下问题。

给你一个字符串$$$s$$$,长度为$$$n$$$,由小写英文字母和问号组成。是否可以用小写英文字母替换问号,使得字符串“abacaba”作为结果字符串中的子字符串恰好出现一次?

每个问号应替换为恰好一个小写英文字母。例如,字符串“a?b?c”可以转换为字符串“aabbc”和“azbzc”,但不能转换为字符串“aabc”、“a?bbc”和“babbc”。

长度为 $$$m$$$ 的字符串 $$$t$$$ 在长度为 $$$n$$$ 的字符串 $$$s$$$ 中作为子字符串的出现是索引 $$$i$$$ ($$$1 \leq i \leq n - m + 1$$$),使得字符串 $$$s[i..i+m-1]$$$ 组成从$$$i$$$开始的$$$m$$$连续符号$$$s$$$等于字符串$$$t$$$。例如,字符串“ababa”在 $$$i = 1$$$ 和 $$$i = 3$$$ 中两次出现字符串“aba”作为子字符串,但在字符串“acba”中没有出现字符串“aba”作为子字符串。

请帮助 Acacius 检查是否可以将所有问号替换为小写英文字母,从而使字符串“abacaba”作为子字符串在结果字符串中仅出现一次。

输入

输入的第一行包含一个整数 $$$T$$$ ($$$1 \leq T \leq 5000$$$),测试用例的数量。 $$$T$$$ 后面是带有测试用例描述的行。

测试用例描述的第一行包含单个整数 $$$n$$$ ($$$7 \leq n \leq 50$$$),字符串长度 $$$s$$$。

测试用例描述的第二行包含字符串$$$s$$$,长度为$$$n$$$,由小写英文字母和问号组成。

输出

对于每个测试用例,输出一个答案。

如果无法将字符串 $$$s$$$ 中的问号替换为小写英文字母,则结果字符串中恰好出现一次字符串“abacaba”作为子字符串输出“No”。

否则输出“Yes”,并在下一行输出由 $$$n$$$ 小写英文字母组成的结果字符串。如果有多个可能的字符串,则输出任何一个。

您可以在任何情况下打印“Yes”和“No”中的每个字母(因此,例如,字符串 yEs、yes、Yes 和 YES 都将被识别为肯定答案)。

示例

输入 #1

6
7
abacaba
7
???????
11
aba?abacaba
11
abacaba?aba
15
asdf???f???qwer
11
abacabacaba

输出 #1

Yes
abacaba
Yes
abacaba
Yes
abadabacaba
Yes
abacabadaba
No
No

注意

在第一个示例中,字符串“abacaba”作为子字符串在字符串“abacaba”中恰好出现一次。

在第二个示例中,七个问号可以替换为任意七个小写英文字母,特别是“abacaba”。

在第六个示例中,字符串“abacaba”作为子字符串出现了两次。