题目描述

给定一个长度为 $3N$ 的字符串 $S$，其中 $S$ 恰好包含 $N$ 个 A、$N$ 个 B 和 $N$ 个 C。

我们称一个由 A、B、C 组成的字符串 $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$

输出格式

请输出一个长度为 $3N$ 的、仅包含 $1$ 到 $6$ 的数字的字符串。对于每个 $1 \leq i \leq 6$，将 $S$ 中对应输出为 $i$ 的字符按顺序取出，组成的子序列应为好字符串。若有多种答案，输出任意一种均可。

样例 1

输入

2
ABCCBA

输出

111222

样例 2

输入

4
AABCBCAACBCB

输出

111211241244

说明/提示

限制

• $1 \leq N \leq 2 \cdot 10^5$
• 字符串 $S$ 恰好包含 $N$ 个 A、$N$ 个 B、$N$ 个 C。

样例解释 1

$S$ 被分为子序列 ABC 和 CBA，它们都是好字符串。

样例解释 2

输出为 $1$ 的位置对应的子序列为 AABBCC，输出为 $2$ 的位置对应的子序列为 CAB，输出为 $4$ 的位置对应的子序列为 ACB，它们都是好字符串。

由 ChatGPT 4.1 翻译