This is the hard version of the problem. The difference between the versions is that in this version, there is no restriction on the number of question marks. You can hack only if you solved all versions of this problem. For a long time, no one could decipher Sumerian cuneiform. However, it has finally succumbed to pressure! Today, you have the chance to decipher Yandex cuneiform. Yandex cuneiform is defined by the following rules: An empty string is a Yandex cuneiform. If you insert exactly one copy of each of the three letters ' Y ', ' D ', and ' X ' into a Yandex cuneiform in such a way that no two adjacent letters become equal after the operation, you obtain a Yandex cuneiform. If a string can't be obtained using the above rules, it is not a Yandex cuneiform. You are given a template. A template is a string consisting of the characters ' Y ', ' D ', ' X ', and ' ? '. You need to check whether there exists a way to replace each question mark with ' Y ', ' D ', or ' X ' to obtain a Yandex cuneiform, and if it exists, output any of the matching options, as well as a sequence of insertion operations to obtain the resulting cuneiform. In this version of the problem, the number of question marks in the template can be arbitrary. Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 5 \cdot 10^4)). The description of the test cases follows. Each test case consists of a single line containing a template of length (n) ((3 \leq n < 2 \cdot 10^5), (n \bmod 3 = 0)), consisting only of characters ' Y ', ' D ', ' X ', and ' ? '. It is guaranteed that the sum of (n) over all test cases does not exceed (2 \cdot 10^5). For each test case, output a single line containing ' NO ' if it is not possible to obtain a cuneiform from the given template. Otherwise, output ' YES ' on the first line, and on the second line, any obtainable cuneiform. After that, you need to output the sequence of opera