Bessie có một chiếc máy tính với bàn phím chỉ có hai chữ cái là M và O.

Bessie muốn gõ tiếng bò yêu thích của mình là \(S\), gồm \(N\) chữ cái, mỗi chữ cái là M hoặc O. Tuy nhiên, máy tính của cô đã bị nhiễm vi-rút. Mỗi khi cô cố gõ chữ O, mọi chữ cái cô đã gõ từ trước đến lúc đó đều bị đảo, từ M thành O hoặc từ O thành M, rồi chữ O mới xuất hiện.

Liệu Bessie có thể gõ được tiếng bò yêu thích của mình hay không?

Ngoài ra, Bessie được cho một tham số \(k\) có giá trị bằng \(0\) hoặc \(1\).

• Nếu \(k=0\), Bessie chỉ cần xác định liệu có thể gõ được tiếng bò yêu thích của mình hay không.
• Nếu \(k=1\), Bessie còn phải đưa ra một ví dụ về dãy phím cần nhấn để gõ được tiếng bò yêu thích của mình.

Dữ liệu vào

Dòng đầu tiên chứa \(T\), số lượng bộ test độc lập (\(1\le T\le 10^4\)), và \(k\) (\(0\le k\le 1\)).

Dòng đầu tiên của mỗi bộ test chứa \(N\) (\(1\le N\le 2\cdot 10^5\)).

Dòng thứ hai của mỗi bộ test chứa \(S\). Đảm bảo rằng \(S\) không chứa ký tự nào ngoài M và O.

Tổng \(N\) trên tất cả các bộ test không vượt quá \(4\cdot 10^5\).

Dữ liệu ra

Với mỗi bộ test, hãy in một hoặc hai dòng theo quy trình sau.

Nếu Bessie không thể gõ được \(S\), hãy in NO trên một dòng.

Ngược lại, ở dòng đầu tiên hãy in YES. Ngoài ra, nếu \(k=1\), ở dòng thứ hai hãy in một xâu độ dài \(N\), gồm các ký tự theo đúng thứ tự Bessie cần gõ để tạo ra tiếng bò yêu thích của mình. Nếu có nhiều xâu thỏa mãn, có thể in bất kỳ xâu nào.

Ví dụ

2 0
3
MOO
5
OOMOO

YES
YES

2 1
3
MOO
5
OOMOO

YES
OMO
YES
MOOMO

Phân nhóm

• Test 3–4: \(k=0\).
• Test 5–6: \(k=1\), \(T\le 10^3\), \(N\le 10\).
• Test 7–9: \(k=1\), \(T\le 10\), \(N\le 1000\).
• Test 10–16: \(k=1\).

Nguồn

USACO 2026 Contest 2, Bronze Division — bài gốc It's Mooin' Time IV, tác giả: Nick Wu.
https://usaco.org/index.php?page=viewproblem2&cpid=1563