ABC Identity

AtCoder

IDagc055_a

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

2
ABCCBA

Output #1

111222

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

Input #2

4
AABCBCAACBCB

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.

API Response (JSON)

{
  "problem": {
    "name": "ABC Identity",
    "description": {
      "content": "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 fo",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "agc055_a"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a string $S$ of length $3N$, containing exactly $N$ letters `A`, $N$ letters `B`, and $N$ letters `C`.\nLet's call a string $T$ consisting of letters `A`, `B`, and `C` **good**, if the fo...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments