베시는 양의 정수 N과 길이가 3N인 문자열 S를 받는다. S는 길이 3인 문자열 N개를 이어 붙여 만들어지며, 각 길이 3 문자열은 "COW"의 순환 이동(cyclic shift)이다. 즉, 각 문자열은 "COW", "OWC", "WCO" 중 하나이다.

문자열 X가 제곱 문자열(square string)이라는 것은, 어떤 문자열 Y가 존재하여 X = Y + Y 를 만족할 때이자 그때에만 성립한다. 여기서 +는 문자열 이어 붙이기(concatenation)를 의미한다. 예를 들어 "COWCOW"와 "CC"는 제곱 문자열이지만, "COWO"와 "OC"는 제곱 문자열이 아니다.

한 번의 연산에서, 베시는 S에서 어떤 부분수열(subsequence) T를 제거할 수 있는데, 이때 T는 제곱 문자열이어야 한다. 문자열의 부분수열이란, 원래 문자열에서 몇 개(0개일 수도 있음)의 문자를 삭제해서 얻을 수 있는 문자열을 말한다.

당신의 임무는 베시가 S를 빈 문자열로 만들 수 있는지(모든 문자를 제거할 수 있는지) 판단하는 것이다. 또한 가능하다면, 그 방법을 하나 제시해야 한다.

베시는 또한 매개변수 k(0 또는 1)를 받는다. 당신이 제시한 구성에서 사용한 연산 횟수를 M이라고 하자.

k = 0이면, M은 가능한 연산 횟수의 최솟값과 정확히 같아야 한다.
k = 1이면, M은 가능한 최솟값보다 최대 1만큼 더 커도 된다.

#8841 upload 16 done 2 how_to_reg 2 auto_awesome Special judge call_split Subtask

COW Splits timer 1s memory 1024MB

#8841
Special judge

Subtask

COW Splits 1s 1024MB