题目描述

長さ $3N$ の文字列 $S$ が与えられます。$S$ は A, B, C をそれぞれちょうど $N$ 個ずつ含みます。

文字 A, B, C からなる文字列 $T$ が次の条件を満たすとき、$T$ を 良い 文字列であると呼びます。

• $T$ の長さは $3$ で割り切れる。この長さを $3K$ とする。
• $T_1\ =\ T_2\ =\ \ldots\ =\ T_K$
• $T_{K+1}\ =\ T_{K+2}\ =\ \ldots\ =\ T_{2K}$
• $T_{2K+1}\ =\ T_{2K+2}\ =\ \ldots\ =\ T_{3K}$
• 文字 $T_1,\ T_{K+1},\ T_{2K+1}$ は互いに異なる。

良い文字列の例を挙げると、ABC, BBAACC, AAACCCBBB です。

$S$ を $6$ 個以下の（連続とは限らない）部分列に分解する方法であって、各部分列が良い文字列であるような方法を一つ見つけてください。

これは、この問題の制約下で必ず可能であることが証明できます。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $S$

输出格式

1 から 6 までの数字からなる長さ $3N$ の文字列を出力せよ。文字列に含まれる各 $1\le\ i\ \le\ 6$ について、$i$ を出力した位置に対応する $S$ の文字を並べると良い文字列が得られるようにすること。 なお、答えが複数通り存在する場合、そのどれを出力しても正解とみなされる。

题目大意

翻译：

给定长度为 $3n (1 \le n \le 2e5)$ 的序列，其中字母 ABC 各有 $n$ 个。

一个合法序列 $T$ 满足以下条件：

• 其长度为 $3k (1 \le k \le n)$。

• $T_1 = T_2 = ... = T_k$

• $T_{k + 1} = T_{k + 2} = ... = T_{2k}$

• $T_{2k + 1} = T_{2k + 2} = ... = T_{3k}$

• $T_1, T_{k + 1}, T_{2k + 1}$ 互不相同。

求一个把这个序列分成不多于 $6$ 个合法的序列的方案。

可以证明，一定存在一种合法的划分。

2
ABCCBA

111222

4
AABCBCAACBCB

111211241244

提示

制約

• $1\ \le\ N\ \le\ 2\cdot\ 10^5$
• 文字列 $S$ は、文字 A, B, C を $N$ 個ずつ含む。

Sample Explanation 1

$S$ が部分列 ABC, CBA に分割されており、これらはそれぞれ良い文字列です。

Sample Explanation 2

$1$ の位置に対応する部分列は AABBCC、$2$ の位置に対応する部分列は CAB、$4$ の位置に対応する部分列は ACB であり、これらは全て良い文字列です。