F2. Яндексовая клинопись (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии нет ограничений на количество знаков вопроса. Вы можете делать взломы только в том случае, если решили все версии этой задачи.

Долгое время никто не мог расшифровать шумерскую клинопись. Все же она поддалась напору! Сегодня вам выпал шанс расшифровать Яндексовую клинопись.

Яндексовые клинописи задаются следующими правилами:

  1. Пустая строка является Яндексовой клинописью.
  2. Если вставить в Яндексовую клинопись три буквы «Y», «D» и «X» (каждую в одном экземпляре) таким образом, что после применения операции никакие две соседние буквы не стали равны, получится Яндексовая клинопись.
  3. Если строка не может быть получена с помощью описанных выше операций, она не является Яндексовой клинописью.

Вам задается шаблон. Шаблоном называется строка, состоящая из символов «Y», «D», «X» и «?».

Проверьте, существует ли способ заменить каждый знак вопроса на одну букву «Y», «D» или «X» так, чтобы получилась Яндексовая клинопись, и если он существует, выведите любой подходящий вариант, а также последовательность операций вставки, которая приводит к такой строке.

В этой версии задачи количество знаков вопроса может быть произвольным.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$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$$$. Позиция для вставки – это количество символов, которое надо отступить от начала строки для вставки. Например, после вставки символа «D» в строку «YDX» с $$$p=3$$$ получится строка «YDXD», а с $$$p=0$$$ получится строка «DYDX». Заметьте, что индекс не может превышать текущую длину строки.

Операции применяются сверху вниз, слева направо. После вставки очередной тройки символов в получившейся строке не должно быть двух подряд идущих одинаковых символов.

Пример
Входные данные
4
???
Y??D?X
???
D??DXYXYX
Выходные данные
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}$$$.