You are given a string of length , 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 (one of A, B and C). Then, replace all the characters on the subsegment with .
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 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 (1 \le n \le 3 \cdot 10^5).
The second line of the input contains a string of length , consisting of the characters A, B and C.
In the first line print the minimum number of operations .
In the -th of the next lines print 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 -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.
Example 1
Example 2
Example 3
In the first sample, the string will undergo the following transformations:
AAA ABB 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 CCABCABAB. Now, it contains each letter times.