31155번 - Jason ABC 스페셜 저지다국어

문제

You are given a string $S$ of length 3ドルn,ドル consisting of the characters A, B and C. You are allowed to perform the following operation:

• Select some subsegment of this string and a character $c$ (one of A, B and C). Then, replace all the characters on the subsegment with $c$.

Find the smallest number of times that you would have to apply the operation above to get a string which contains each of characters A, B and C exactly $n$ times. It can be shown that it is always possible to get such a string.

In addition, find a sequence of operations of the smallest possible length. If there are many such sequences, you can output any of them.

입력

The first line of input contains a single integer $n$ (1ドル \le n \le 3 \cdot 10^5$).

The second line of the input contains a string $S$ of length 3ドルn,ドル consisting of the characters A, B and C.

출력

In the first line print the minimum number of operations $k$.

In the $i$-th of the next $k$ lines print 2ドル$ integers $l_i, r_i$ and a character $c_i$ (1ドル \le l_i \le r_i \le 3n,ドル $c_i \in \{$A, B, C$\}$), denoting that in the $i$-th operation you will replace each of the characters $S_{l_i}, S_{l_i+1}, \ldots, S_{r_i}$ with $c_i$.

If there is more than one solution with a minimum number of operations, you can print any one of them.

제한

노트

In the first sample, the string will undergo the following transformations:

AAA $\to$ ABB $\to$ ABC.

In the second sample, the string already contains exactly one A, one B and one C.

In the third sample, the string will undergo the following transformation:

ABABCABAB $\to$ CCABCABAB. Now, it contains each letter 3ドル$ times.