【每日一题(8)】Mammoth's Genome Decoding CodeForces - 747B

Mammoth’s Genome Decoding CodeForces - 747B

The process of mammoth’s genome decoding in Berland comes to its end!

One of the few remaining tasks is to restore unrecognized nucleotides in a found chain s. Each nucleotide is coded with a capital letter of English alphabet: ‘A’, ‘C’, ‘G’ or ‘T’. Unrecognized nucleotides are coded by a question mark ‘?’. Thus, s is a string consisting of letters ‘A’, ‘C’, ‘G’, ‘T’ and characters ‘?’.

It is known that the number of nucleotides of each of the four types in the decoded genome of mammoth in Berland should be equal.

Your task is to decode the genome and replace each unrecognized nucleotide with one of the four types so that the number of nucleotides of each of the four types becomes equal.

Input

The first line contains the integer n (4 ≤ n ≤ 255) — the length of the genome.

The second line contains the string s of length n — the coded genome. It consists of characters ‘A’, ‘C’, ‘G’, ‘T’ and ‘?’.

Output

If it is possible to decode the genome, print it. If there are multiple answer, print any of them. If it is not possible, print three equals signs in a row: “===” (without quotes).

Example

Input
8
AG?C??CT
Output
AGACGTCT


Input
4
AGCT
Output
AGCT


Input
6
????G?
Output
===


Input
4
AA??
Output
===

Note

In the first example you can replace the first question mark with the letter ‘A’, the second question mark with the letter ‘G’, the third question mark with the letter ‘T’, then each nucleotide in the genome would be presented twice.

In the second example the genome is already decoded correctly and each nucleotide is exactly once in it.

In the third and the fourth examples it is impossible to decode the genom.

题意

伯尔兰猛犸解码基因组的四种核苷酸数量应该是相等的。您的任务是解码基因组,并用四种类型中的一种替换每个未识别的核苷酸,以使四种类型中的每一种的核苷酸数量相等。
判断4种核苷酸数量有没有可能相等,如果不可能,输出“===”,否则输出正确基因组(如果有多种,只需要输出其中一种)

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<stdio.h>
#include<stdlib.h>
int main(void)
{
int n,i = 0;
while(scanf("%d",&n) != EOF)
{
int a = 0,t = 0,c = 0,g = 0;
char p[255];
//char *p;
//p = (char *)malloc(sizeof(char) * n);
scanf("%s",&p);
for(i = 0;i < n; i++)
{
switch(p[i])
{
case 'A': a++; break;
case 'T': t++; break;
case 'C': c++; break;
case 'G': g++; break;
}
}
if(n%4 == 0)
{
int x = n/4;
if(x >= a && x >= t && x >= c && x >= g)
{
int A = x - a,T = x - t,C = x - c, G = x - g;
for(i = 0;i < n; i++)
{
if(p[i] == '?')
{
if(A != 0)
{
p[i] = 'A';
A--;
//continue;
}
else if(T != 0)
{
p[i] = 'T';
T--;
//continue;
}
else if(C != 0)
{
p[i] = 'C';
C--;
//continue;
}
else if(G != 0)
{
p[i] = 'G';
G--;
//continue;
}
}
}
printf("%s\n",p);
}
else
printf("===\n");
}
else
printf("===\n");
}

return 0;
}