센트컵

센트는 라틴어로 100을 의미하는 켄툼(Centum)에서 유래한 단어이다. 따라서 센트컵은 100개의 컵을 의미한다고 볼 수 있다.

길이가 $N$인 문자열 $S$가 주어진다. 문자열 $S$는 알파벳 대문자로만 이루어져 있으며, 문자의 위치는 왼쪽부터 $1$번에서 $N$번까지이다.

문자열 $S$에서 하나의 컵을 구성하려면 세 위치 $i$, $j$, $k$를 선택해야 한다. 선택한 위치는 다음 조건을 모두 만족해야 한다.

• $i < j < k$
• $S_i = \texttt{C}$
• $S_j = \texttt{U}$
• $S_k = \texttt{P}$

여러분은 문자열 S에서 센트컵, 즉 정확히 100개의 컵을 구성해야 한다. 구성한 컵들을 왼쪽부터 차례대로 $1$번부터 $100$번까지 번호를 매기고, $t$번째 컵을 구성하는 데 사용한 위치를 $i_t$, $j_t$, $k_t$라고 하자. 서로 다른 컵에 사용된 위치가 겹치지 않고 모든 컵이 왼쪽부터 순서대로 배치되도록 다음 조건을 만족해야 한다.

• 모든 $1 \le t < 100$에 대하여 $k_t < i_{t+1}$

하나의 컵을 구성하는 데 사용한 위치가 $i$, $j$, $k$일 때, 해당 컵의 크기를 $k-i$로 정의한다.

100개의 컵을 구성할 수 있다면, 각 컵의 크기의 합이 최대가 되도록 센트컵을 구성하고 그 크기의 합과 구성을 구해보자.

첫 번째 줄에 문자열의 길이를 나타내는 정수 $N$이 주어진다.

두 번째 줄에 알파벳 대문자로만 이루어진 길이 $N$의 문자열 $S$가 주어진다.

만약 조건을 만족하는 $100$개의 컵을 구성할 수 있다면 다음과 같이 출력한다.

• 첫 번째 줄에 $100$개 컵의 크기의 합의 최댓값을 출력한다.
• 두 번째 줄부터 $100$개의 줄에 걸쳐, 컵의 번호가 작은 순서대로 각 컵을 구성하는 세 위치 $i_t$, $j_t$, $k_t$를 공백으로 구분하여 출력한다.

가능한 구성이 여러 개라면 그중 아무 것이나 출력한다.

만약 조건을 만족하는 $100$개의 컵을 구성할 수 없다면 첫 번째 줄에 -1을 출력한다.

• $1 \le N \le 100,000$
• $|S| = N$
• $S$는 알파벳 대문자로만 이루어져 있다.