← 返回题目列表

Codeforces · 1999/D

D. 斯拉夫的考试

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

斯拉夫语考试非常艰难,需要你的帮助才能通过。这是他正在努力解决的问题:

存在一个字符串$$$s$$$,它由小写英文字母和可能零个或多个“?”组成。

斯拉夫语被要求改变每个“?”为小写英文字母,使得字符串 $$$t$$$ 成为字符串 $$$s$$$ 的子序列(不一定是连续的)。

输出任何这样的字符串,或者说如果不存在符合条件的字符串则不可能。

输入

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

每个测试用例的第一行包含一个字符串 $$$s$$$ ($$$1 \leq |s| \leq 2 \cdot 10^5$$$,并且 $$$s$$$ 仅由小写英文字母和“?”-s) – 您拥有的原始字符串。

每个测试用例的第二行包含一个字符串 $$$t$$$ ($$$1 \leq |t| \leq |s|$$$,并且 $$$t$$$ 仅包含小写英文字母) – 该字符串应该是字符串 $$$s$$$ 的子序列。

所有测试用例的 $$$|s|$$$ 总和不超过 $$$2 \cdot 10^5$$$,其中 $$$|x|$$$ 表示字符串 $$$x$$$ 的长度。

输出

对于每个测试用例,如果语句中描述的不存在这样的字符串,则输出“NO”(不带引号)。

否则,输出“YES”(不带引号)。然后,输出一行——符合所有条件的字符串。

在任何情况下都可以输出“YES”和“NO”(例如,字符串“yEs”、“yes”和“Yes”将被识别为肯定响应)。

如果可能有多个答案,则可以输出其中任何一个。

示例

输入 #1

5
?????
xbx
ab??e
abcde
ayy?x
a
ab??e
dac
paiu
mom

输出 #1

YES
xabax
YES
abcde
YES
ayyyx
NO
NO