配点 : $400$ 点

問題文

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

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

制約

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

入力

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

$N$

$S$

出力

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

2
ABCCBA

111222

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

4
AABCBCAACBCB

111211241244

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