A - ABC Identity Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 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 の文字を並べると良い文字列が得られるようにすること。 なお、答えが複数通り存在する場合、そのどれを出力しても正解とみなされる。

入力例 1

2
ABCCBA

出力例 1

111222

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

入力例 2

4
AABCBCAACBCB

出力例 2

111211241244

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

Score : 400 points

Problem Statement

You are given a string S of length 3N, containing exactly N letters A, N letters B, and N letters C.

Let's call a string T consisting of letters A, B, and C good, if the following conditions hold:

  • The length of T is divisible by 3. Let's denote it by 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}.
  • Letters T_1, T_{K+1} and T_{2K+1} are different from each other.

Examples of good strings are ABC, BBAACC, and AAACCCBBB.

Find a way to split S into at most 6 (not necessarily contiguous) subsequences so that the letters from each subsequence form a good string.

It can be proved that, under the constraints of the problem, it's always possible.

Constraints

  • 1 \le N \le 2\cdot 10^5
  • The string S contains N letters A, N letters B, and N letters C.

Input

Input is given from Standard Input in the following format:

N
S

Output

Output a string of length 3N, containing only digits from 1 to 6. For every 1\le i \le 6 which appears in your string, characters of S at positions where you output i have to form a good string. If there are multiple possible solutions, printing any of them will be considered correct.

Sample Input 1

2
ABCCBA

Sample Output 1

111222

S is split into subsequences ABC and CBA, and each of them is a good string.

Sample Input 2

4
AABCBCAACBCB

Sample Output 2

111211241244

Positions of 1 form a subsequence AABBCC, positions of 2 form a subsequence CAB, and positions of 4 form a subsequence ACB. All of these strings are good.