CF2046F1 Yandex Cuneiform (Easy 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$。

对于每个测试用例，如果无法通过上述规则得到 Yandex 楔形文字，输出一行 'NO'。 否则，第一行输出 'YES'，第二行输出任意一个可行的楔形文字。之后输出一组插入操作序列，描述如何得到你输出的楔形文字。 插入操作序列由 $\frac{n}{3}$ 组三元组组成。每个三元组包含三个对，每个对的形式为 $c\ p$，其中 $c$ 是 'Y'、'D' 或 'X' 中的一个字母，$p$ 表示插入该字母的位置。插入位置 $p$ 表示从字符串开头跳过 $p$ 个字符后插入。例如，在字符串 "YDX" 中插入字符 'D' 且 $p=3$，结果为 "YDXD"；若 $p=0$，则结果为 "DYDX"。注意，插入位置不能超过当前字符串长度。 所有操作按从上到下、从左到右的顺序依次执行。每次插入三元组后，字符串中不应出现两个相邻的相同字符。

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