← 返回题目列表

Codeforces · 2046/F2

F2. Yandex 楔形文字(硬版)

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

这是问题的困难版本。版本之间的区别在于,在这个版本中,对问号的数量没有限制。只有解决了该问题的所有版本,您才能破解。

很长一段时间以来,没有人能够破译苏美尔楔形文字。然而,最终还是屈服于压力!今天,您有机会破译 Yandex 楔形文字。

Yandex 楔形文字由以下规则定义:

1. 空字符串是 Yandex 楔形文字。
2. 如果您将三个字母“Y”、“D”和“X”中的每一个精确插入到 Yandex 楔形文字中,并且操作后没有两个相邻字母变得相等,您将获得 Yandex 楔形文字。
3. 如果使用上述规则无法获得字符串,则它不是 Yandex 楔形文字。

为您提供了一个模板。模板是由字符“Y”、“D”、“X”和“?”组成的字符串。

您需要检查是否存在一种方法将每个问号替换为“Y”、“D”或“X”以获得Yandex楔形文字,如果存在,则输出任何匹配选项以及一系列插入操作以获得结果楔形文字。

在此版本的问题中,模板中问号的数量可以是任意的。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$)。测试用例的描述如下。

每个测试用例由一行包含长度为 $$$n$$$ ($$$3 \leq n < 2 \cdot 10^5$$$, $$$n \bmod 3 = 0$$$) 的模板组成,仅包含字符“Y”、“D”、“X”和“?”。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果无法从给定模板获取楔形文字,则输出包含“NO”的单行。

否则,在第一行输出“YES”,在第二行输出任何可获得的楔形文字。之后,您需要输出导致您打印的楔形文字的操作序列。

操作序列由 $$$\frac{n}{3}$$$ 三元对描述。一对的形式为 c p,其中 $$$c$$$ 是字母 'Y'、'D' 或 'X' 之一,$$$p$$$ 是字母 $$$c$$$ 应插入的位置。插入位置是为了插入而从字符串开头跳过的字母数。例如,用$$$p=3$$$将字符“D”插入字符串“YDX”后,结果为“YDXD”,用$$$p=0$$$将结果为“DYDX”。请注意,索引不能超过字符串的当前长度。

操作是从上到下、从左到右进行的。将每个三元组插入到字符串后,不应有两个相邻的相同字符。

示例

输入 #1

4
???
Y??D?X
???
D??DXYXYX

输出 #1

YES
YDX
X 0 D 0 Y 0 
YES
YDXDYX
X 0 Y 0 D 1
X 2 D 3 Y 4
YES
YDX
Y 0 D 1 X 2
NO

注意

在第二个示例中,字符串转换如下:$$$"" \to \mathtt{YDX} \to \mathtt{YDXDYX}$$$。