Bessie has a computer with a keyboard that only has two letters, M and O.
Bessie wants to type her favorite moo S consisting of N letters, each of which is either an M or an O. However, her computer has been hit with a virus. Every time she tries to type the letter O, every letter that she has typed so far flips, either from M to O or from O to M, before the O appears.
Is it possible for Bessie to type out her favorite moo?
Additionally, Bessie is given a parameter k which is either 0 or 1.
If k=0, then Bessie only needs to determine whether it is possible to type out her favorite moo.
If k=1, then Bessie also needs to give an example of a sequence of keystrokes to type so she can type out her favorite moo.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains T, the number of independent test cases (1≤T≤104) and k
(0≤k≤1).
The first line of each test case has N (1≤N≤2⋅105).
The second line of each test case has S. It is guaranteed that no characters will appear in S besides M and O.
The sum of N across all test cases will not exceed 4⋅105.
OUTPUT FORMAT (print output to the terminal / stdout):
For each test case, output either one or two lines using the following procedure.
If it is impossible for Bessie to type out S, print NO on a single line.
Otherwise, on the first line print YES. Furthermore, if k=1, on the second line,print a string of length N, the characters in order that Bessie needs to type in order to type out her favorite moo. If there are multiple such strings, any will be accepted.
SAMPLE INPUT:
2 0
3
MOO
5
OOMOO
SAMPLE OUTPUT:
YES
YES
SAMPLE INPUT:
2 1
3
MOO
5
OOMOO
SAMPLE OUTPUT:
YES
OMO
YES
MOOMO
As Bessie types out MOOMO, this is how the letters change:
1.Before typing the first M, Bessie has an empty string. Afterwards, she has the string M.
2.After typing the first O, the M flips to O, and then the O is appended to form OO.
3.After typing the second O, the OO flips to MM, and then the O is appended to form MMO.
4.After typing the second M, Bessie has the string MMOM.
5.After typing the last O, the string MMOM flips to OOMO, and then the O is appended to form OOMOO, as desired.
SCORING:
Inputs 3-4: k=0.
Inputs 5-6: k=1,T≤103,N≤10.
Inputs 7-9: k=1,T≤10,N≤1000.
Inputs 10-16: k=1.
Problem credits: Nick Wu