문제

지안이는 양의 정수 $N$과 길이가 $3N$인 문자열 $S$를 가지고 있다. $S$는 COW, OWC, WCO 중 하나인 길이 $3$의 문자열 $N$개를 이어 붙여 만든 것이다. 즉, $S$를 구성하는 각 단위는 COW를 순환 이동(cyclic shift)하여 만들 수 있는 문자열이다.

문자열 $X$가 제곱 문자열인 것은 $X = Y + Y$를 만족하는 문자열 $Y$가 존재한다는 것과 같다. 여기서 $+$는 문자열 이어 붙이기를 의미한다. 예를 들어, COWCOW와 CC는 제곱 문자열이지만, COWO와 OC는 아니다.

지안이는 한 번의 연산으로 $S$에서 제곱 문자열인 부분 수열 $T$를 하나 골라 제거할 수 있다. 문자열의 부분 수열이란, 기존 문자열에서 $0$개 이상의 문자를 제거하여 얻을 수 있는 문자열을 말한다.

지안이를 도와 $S$를 빈 문자열로 만드는 것이 가능한지 판단하고, 가능하다면 그 방법을 구하시오.

또한, $0$ 또는 $1$의 값을 갖는 매개변수 $k$가 주어진다. 사용한 연산 횟수를 $M$이라고 하자.

• $k = 0$이라면, $M$은 가능한 최소 연산 횟수와 같아야 한다.
• $k = 1$이라면, $M$은 가능한 최소 연산 횟수보다 최대 $1$만큼 더 클 수 있다. ($M \le$ 최소 연산 횟수 $+ 1$)

입력

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

각 테스트 케이스는 다음과 같이 두 줄로 구성된다.

• 첫째 줄에 $N$이 주어진다. ($1 \le N \le 10^5$)
• 둘째 줄에 문자열 $S$가 주어진다.

모든 테스트 케이스에 대한 $N$의 합은 $10^5$를 넘지 않는다.

출력

각 테스트 케이스에 대해, 다음과 같이 한 줄 또는 두 줄을 출력한다.

$S$를 빈 문자열로 만드는 것이 불가능하다면, -1을 출력한다.

가능하다면, 첫째 줄에 사용한 연산 횟수 $M$을 출력한다. 둘째 줄에 $3N$개의 정수를 공백으로 구분하여 출력한다. $i$번째 정수 $x$는 $S$의 $i$번째 문자가 $x$번째 연산에서 제거되었음을 의미한다. ($1 \le x \le M$)

예제 입력 1

3 1
3
COWOWCWCO
4
WCOCOWWCOCOW
6
COWCOWOWCOWCOWCOWC

예제 출력 1

-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

예제 입력 2

3 0
3
COWOWCWCO
4
WCOCOWWCOCOW
6
COWCOWOWCOWCOWCOWC

예제 출력 2

-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

점수

• 입력 3-4: $T \le 10$, $N \le 6$, $k = 0$
• 입력 5-6: $k = 1$
• 입력 7-14: $k = 0$