문제

현욱이는 M과 O 두 개의 문자만 있는 키보드를 가지고 있다.

현욱이는 M과 O로 이루어진 길이 $N$의 문자열 $S$를 입력하려고 한다. 하지만 현욱이의 컴퓨터가 바이러스에 걸려 작동 방식이 변했다.

현욱이가 O를 입력할 때마다, 이전에 입력했던 모든 문자가 반전된 후 새로운 문자 O가 마지막에 추가된다. 여기서 반전이란 M은 O로, O는 M으로 바뀌는 것을 의미한다. M을 입력할 때는 반전 없이 문자 M만 추가된다.

현욱이가 원하는 문자열 $S$를 입력할 수 있는지 확인하자.

또한, 매개변수 $k$가 주어지는데, 이는 $0$ 또는 $1$이다.

• $k = 0$이면, 현욱이가 원하는 문자열 $S$를 입력할 수 있는지만 판단한다.
• $k = 1$이면, $S$를 입력할 수 있는지 판단하고, 가능하다면 어떤 순서로 키를 눌러야 하는지도 구한다.

입력

첫째 줄에 테스트 케이스의 개수 $T$와 매개변수 $k$가 공백으로 구분되어 주어진다. ($1 \le T \le 10^4$; $0 \le k \le 1$)

각 테스트 케이스의 첫째 줄에 문자열의 길이 $N$이 주어진다. ($1 \le N \le 2 \cdot 10^5$)

둘째 줄에 M과 O로만 이루어진 길이 $N$인 문자열 $S$가 주어진다.

모든 테스트 케이스에 대한 $N$의 합은 $4 \cdot 10^5$을 초과하지 않는다.

출력

각 테스트 케이스마다 다음 절차에 따라 한 줄 또는 두 줄을 출력한다.

현욱이가 문자열 $S$를 입력할 수 없다면 NO를 출력한다.

가능하다면 첫째 줄에 YES를 출력한다. 또한 $k=1$인 경우, 둘째 줄에 현욱이가 $S$를 입력하기 위해 눌러야 하는 키의 순서를 나타내는 길이 $N$인 문자열을 출력한다. 가능한 답이 여러 가지라면 그중 하나를 출력한다.

예제 입력 1

2 0
3
MOO
5
OOMOO

예제 출력 1

YES
YES

예제 입력 2

2 1
3
MOO
5
OOMOO

예제 출력 2

YES
OMO
YES
MOOMO

점수

• 입력 3-4: $k=0$
• 입력 5-6: $k=1$, T ge 10^3, N ge 10
• 입력 7-9: $k=1$, T ge 10, N ge 1\,000
• 입력 10-16: $k=1$