Bessie được cho một số nguyên dương \(N\) và một xâu \(S\) có độ dài \(3N\), được tạo bằng cách nối \(N\) xâu độ dài \(3\), trong đó mỗi xâu là một phép dịch vòng của COW. Nói cách khác, mỗi xâu sẽ là COW, OWC hoặc WCO.

Xâu \(X\) là một xâu bình phương khi và chỉ khi tồn tại một xâu \(Y\) sao cho \(X=Y+Y\), trong đó \(+\) biểu thị phép nối xâu. Chẳng hạn, COWCOW và CC là các xâu bình phương, còn COWO và OC thì không.

Trong một thao tác, Bessie có thể xóa khỏi \(S\) một dãy con \(T\) bất kỳ, với \(T\) là một xâu bình phương. Dãy con của một xâu là xâu có thể thu được bằng cách xóa một số (có thể bằng không) ký tự khỏi xâu ban đầu.

Nhiệm vụ của bạn là giúp Bessie xác định liệu có thể biến \(S\) thành xâu rỗng hay không. Ngoài ra, nếu có thể, bạn phải đưa ra một cách thực hiện.

Bessie còn được cho một tham số \(k\) bằng \(0\) hoặc \(1\). Gọi \(M\) là số thao tác trong cách thực hiện của bạn.

• Nếu \(k=0\), \(M\) phải bằng số thao tác nhỏ nhất có thể.
• Nếu \(k=1\), \(M\) có thể nhiều hơn số thao tác nhỏ nhất có thể không quá một thao tác.

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 10^5\)).

Dòng thứ hai của mỗi bộ test chứa \(S\).

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

Dữ liệu ra

Với mỗi bộ test, in một hoặc hai dòng theo quy tắc sau.

Nếu không thể biến \(S\) thành xâu rỗng, in \(-1\) trên một dòng duy nhất.

Ngược lại, trên dòng đầu tiên, in \(M\) — số thao tác trong cách thực hiện của bạn. Trên dòng thứ hai, in \(3N\) số nguyên cách nhau bởi dấu cách. Số nguyên thứ \(i\), ký hiệu là \(x\), cho biết ký tự thứ \(i\) của \(S\) được xóa trong dãy con của thao tác thứ \(x\) (\(1\le x\le M\)).

Ví dụ

3 1
3
COWOWCWCO
4
WCOCOWWCOCOW
6
COWCOWOWCOWCOWCOWC

-1
1
1 1 1 1 1 1 1 1 1 1 1 1
3
3 3 2 3 3 2 1 1 1 1 1 1 1 1 1 1 1 1

3 0
3
COWOWCWCO
4
WCOCOWWCOCOW
6
COWCOWOWCOWCOWCOWC

-1
1
1 1 1 1 1 1 1 1 1 1 1 1
2
1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2

Phân nhóm

• Input 3–4: \(T\le 10\), \(N\le 6\), \(k=0\).
• Input 5–6: \(k=1\).
• Input 7–14: \(k=0\).

Nguồn

USACO 2026 Contest 1, Bronze, bài COW Splits. Tác giả: Aakash Gokhale.
https://usaco.org/index.php?page=viewproblem2&cpid=1540