给你一个长度为 $3n$ 的字符串 $S$，由字符 A、B 和 C 组成。你可以进行以下操作：

• 选择该字符串的一个子段和一个字符 $c$（A、B 或 C 之一）。然后，将该子段上的所有字符替换为 $c$。

找到最少的操作次数，使得操作后的字符串中字符 A、B 和 C 各恰好出现 $n$ 次。可以证明，总是可以得到这样的字符串。

此外，请找出一条长度最小的操作序列。如果存在多个这样的序列，你可以输出其中任意一个。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$）。

第二行包含一个长度为 $3n$ 的字符串 $S$，由字符 A、B 和 C 组成。

输出格式

第一行输出最少的操作次数 $k$。

接下来的 $k$ 行中，第 $i$ 行输出两个整数 $l_i, r_i$ 和一个字符 $c_i$（$1 \le l_i \le r_i \le 3n$，$c_i \in \{\text{A}, \text{B}, \text{C}\}$），表示在第 $i$ 次操作中，你将字符 $S_{l_i}, S_{l_i+1}, \dots, S_{r_i}$ 替换为 $c_i$。

如果存在多个具有最少操作次数的解，你可以输出其中任意一个。

样例

输入样例 1

1
AAA

输出样例 1

2
2 3 B
3 3 C

输入样例 2

1
CAB

输出样例 2

0

输入样例 3

3
ABABCABAB

输出样例 3

1
1 2 C

说明

在第一个样例中，字符串将经历以下变化： AAA $\to$ ABB $\to$ ABC。

在第二个样例中，字符串已经恰好包含一个 A、一个 B 和一个 C。

在第三个样例中，字符串将经历以下变化： ABABCABAB $\to$ CCABCABAB。现在，它包含每个字母各 3 次。