Mùa Moo IV

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Bessie có một bàn phím chỉ có hai phím: M và O. Cô ấy muốn gõ một chuỗi yêu thích $S$ gồm $N$ ký tự (chỉ chứa M và O).

Tuy nhiên, bàn phím bị nhiễm virus. Mỗi khi Bessie nhấn phím O, trước khi ký tự O được thêm vào cuối chuỗi, tất cả các ký tự đã gõ trước đó sẽ bị đảo ngược (M thành O và O thành M). Phím M hoạt động bình thường (chỉ thêm M vào cuối).

Hãy xác định xem Bessie có thể gõ được chuỗi $S$ hay không, và nếu có, hãy đưa ra một dãy phím hợp lệ.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $T$ và $k$ ( $1 \leq T \leq 10^{4}$ , $k \in {0, 1}$ ).
Với mỗi test case:
- Dòng 1: Số nguyên $N$ ( $1 \leq N \leq 2 \times 10^{5}$ ).
- Dòng 2: Chuỗi $S$ gồm $N$ ký tự M hoặc O.

Tổng $N$ trên tất cả test case không vượt quá $4 \times 10^{5}$ .

Dữ liệu ra

Với mỗi test case:

Nếu không thể gõ được chuỗi $S$ : in NO.
Nếu có thể: in YES.
Nếu $k = 1$ và đáp án là YES: in thêm dòng thứ hai là dãy phím cần nhấn (chuỗi gồm $N$ ký tự M hoặc O).

Ràng buộc

$1 \leq T \leq 10^{4}$
$1 \leq N \leq 2 \times 10^{5}$
Tổng $N \leq 4 \times 10^{5}$

Ví dụ

Input	Output	Giải thích
2 0 3 MOO 5 OOMOO	YES YES	Luôn tồn tại cách gõ.
2 1 3 MOO 5 OOMOO	YES OMO YES MOOMO	Test case 1: Nhấn O -> "O", nhấn M -> "OM", nhấn O -> đảo "OM" thành "MO" rồi thêm O -> "MOO". Test case 2: Nhấn M -> "M", nhấn O -> đảo "M" thành "O" rồi thêm O -> "OO", nhấn O -> đảo "OO" thành "MM" rồi thêm O -> "MMO", nhấn M -> "MMOM", nhấn O -> đảo "MMOM" thành "OOMO" rồi thêm O -> "OOMOO".

Ghi chú

Đáp án luôn là YES - luôn tồn tại cách gõ hợp lệ.

Bình luận

Không có bình luận tại thời điểm này.