← 返回题目列表

Codeforces · 747/B

B. 猛犸象的基因组解码

中文机器翻译题面 查看原题

伯兰​​德猛犸象基因组解码进程告一段落!

剩下的几个任务之一是恢复已发现的链中未识别的核苷酸。每个核苷酸都用英文字母的大写字母编码:“A”、“C”、“G”或“T”。未识别的核苷酸由问号“?”编码。因此,s 是由字母“A”、“C”、“G”、“T”和字符“?”组成的字符串。

已知伯兰德猛犸象基因组解码中四种类型的核苷酸数量应该是相等的。

你的任务是解码基因组,并用四种类型中的一种替换每个无法识别的核苷酸,以便四种类型中每种类型的核苷酸数量相等。

输入

第一行包含整数 n (4 ≤ n ≤ 255) — 基因组的长度。

第二行包含长度为 n 的字符串 s — 编码的基因组。它由字符“A”、“C”、“G”、“T”和“?”组成。

输出

如果可以解码基因组,请将其打印出来。如果有多个答案,请打印其中一个。如果不可能,请连续打印三个等号:“===”(不带引号)。

示例

输入 #1

8
AG?C??CT

输出 #1

AGACGTCT

输入 #2

4
AGCT

输出 #2

AGCT

输入 #3

6
????G?

输出 #3

===

输入#4

4
AA??

输出#4

===

注意

在第一个示例中,您可以将第一个问号替换为字母“A”,将第二个问号替换为字母“G”,将第三个问号替换为字母“T”,然后基因组中的每个核苷酸将出现两次。

在第二个示例中,基因组已被正确解码,并且每个核苷酸在其中仅出现一次。

在第三个和第四个示例中,不可能解码基因组。