CF2046F2 Yandex Cuneiform (Hard Version)

这是该问题的困难版本。不同之处在于本版本对问号的数量没有限制。只有在你解决了所有版本的问题后，才能进行 hack。 很长一段时间里，没有人能破译苏美尔楔形文字。然而，它终于屈服于压力！今天，你有机会破译 Yandex 楔形文字。 Yandex 楔形文字由以下规则定义： 1. 空字符串是 Yandex 楔形文字。 2. 如果你在一个 Yandex 楔形文字中，恰好插入一份 'Y'、'D'、'X' 三个字母各一份，并且插入后没有两个相邻的字母相同，那么你得到的字符串也是 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$ 是插入该字母的位置。插入位置指的是从字符串开头跳过 $p$ 个字符后插入。例如，在字符串 "YDX" 中插入字符 'D'，$p=3$ 时结果为 "YDXD"，$p=0$ 时结果为 "DYDX"。注意，索引不能超过当前字符串长度。 操作按从上到下、从左到右的顺序依次应用。每次插入一个三元组后，字符串中不应出现两个相邻且相同的字符。

在第二个样例中，字符串的变化过程如下：$"" \to \mathtt{YDX} \to \mathtt{YDXDYX}$。 由 ChatGPT 4.1 翻译