题目描述

给定一个长度为 $3N$ 的字符串 $S$，包含 $N$ 个字母 A，$N$ 个字母 B 和 $N$ 个字母 C。

如果满足以下条件，我们称字符串 $T$（由字母 A，B 和 C 组成）是good的：

• $T$ 的长度可以被 $3$ 整除，记为 $3K$。
• 对于 $1 \leq i \leq K$，有 $T_i = T_{i+K} = T_{i+2K}$。
• 字母 $T_1, T_{K+1}$ 和 $T_{2K+1}$ 三者各不相同。

例如，ABC，BBAACC 和 AAACCCBBB 都是 good 字符串。

找到一种划分方式，将字符串 $S$ 划分为最多 $6$ 个（不一定连续）子序列，使得每个子序列中的字母形成一个 good 字符串。

可以证明，在问题的约束条件下，总是存在这样的划分方式。

约束条件

• $1 \le N \le 2 \times 10^5$
• 字符串 $S$ 包含 $N$ 个字母 A，$N$ 个字母 B 和 $N$ 个字母 C。

输入

从标准输入读入数据，数据格式如下：

$N$ $S$

输出

输出一个长度为 $3N$ 的字符串，仅包含数字 1 到 6。对于输出字符串中的每个 $1\le i \le 6$，在输出的位置上对应的 $S$ 中的字符必须形成一个 good 字符串。如果有多个可能的解答，任意输出一个即可。

示例输入 1

2
ABCCBA

示例输出 1

111222

将 $S$ 划分为子序列 ABC 和 CBA，它们都是 good 字符串。

示例输入 2

4
AABCBCAACBCB

示例输出 2

111211241244

数字 1 的位置形成子序列 AABBCC，数字 2 的位置形成子序列 CAB，数字 4 的位置形成子序列 ACB。这些子序列都是 good 字符串。