COW Splits
Bessie is given a positive integer N and a string S of length 3N which is generated by concatenating N strings of length 3, each of which is a cyclic shift of "COW". In other words, each string will be "COW", "OWC", or "WCO".
String X is a square string if and only if there exists a string Y such that X=Y+Y where + represents string concatenation. For example, "COWCOW" and "CC" are examples of square strings but "COWO" and "OC" are not.
In a single operation, Bessie can remove any subsequence T from S where T is a square string. A subsequence of a string is a string which can be obtained by removing several (possibly zero) characters from the original string.
Your job is to help Bessie determine whether it is possible to transform S into an empty string. Additionally, if it is possible, then you must provide a way to do so.
Bessie is also given a parameter k which is either 0 or 1. Let M be the number of operations in your construction.
- If k=0, then M must equal the minimum possible number of operations.
- If k=1, then M can be up to one plus the minimum possible number of operations
For the last test, the optimal number of operations is two, so any valid construction with either M=2 or M=3 would be accepted.
For M=3, here is a possible construction:
- In the first operation, remove the last twelve characters. Now we're left with COWCOW.
- In the second operation, remove the subsequence WW. Now we're left with COCO.
- In the last operation, remove all remaining characters.
SCORING:
- Inputs 3-4: T≤10,N≤6,k=0
- Inputs 5-6: k=1
- Inputs 7-14: k=0
Problem credits: Aakash Gokhale
Source: USA Computing Olympiad.
Input Format
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≤105).
The second line of each test case has S.
The sum of N across all test cases will not exceed 105.
Output Format
For each test case, output either one or two lines using the following procedure.
If it is impossible to transform S into an empty string, print −1 on a single line.
Otherwise, on the first line print M -- the number of operations in your construction. On the second line, print 3N space-separated integers. The ith integer x indicates that the ith letter of S was deleted as part of the xth subsequence (1≤x≤M).