Jason ABC#13031

Jason ABC

You are given a string of length , consisting of the characters A, B and C. You are allowed to perform the following operation:

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.

Input

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.

Output

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.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Example 3

Loading
Loading

Note

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.