409118: GYM103439 J Jason ABC

You are given a string $$$S$$$ of length $$$3n$$$, 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 $$$3n$$$, 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 \{\texttt{A}, \texttt{B}, \texttt{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.

1
AAA

2
2 3 B
3 3 C

1
CAB

0

3
ABABCABAB

1
1 2 C

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.