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).


-----Examples-----
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.

Difficulty: interview

Starter code:

Solutions:

import sys
#sys.stdin=open("data.txt")
input=sys.stdin.readline

n=int(input())
if n%4: print("===")
else:
    t=input().strip()
    a=[n//4]*4
    for i in t:
        if i=='A': a[0]-=1
        elif i=='C': a[1]-=1
        elif i=='G': a[2]-=1
        elif i=='T': a[3]-=1
    if min(a)<0: print("===")
    else:
        out=[]
        for i in t:
            if i=='?':
                if a[0]:
                    out.append('A')
                    a[0]-=1
                elif a[1]:
                    out.append('C')
                    a[1]-=1
                elif a[2]:
                    out.append('G')
                    a[2]-=1
                elif a[3]:
                    out.append('T')
                    a[3]-=1
            else: out.append(i)
        print("".join(out))


x=int(input())
if x%4 != 0:
    print("==="); quit();

ct = x//4;
s = input()
aa = s.count('A')-ct
cc = s.count('C')-ct
gg = s.count('G')-ct
tt = s.count('T')-ct
aa=-aa;cc=-cc;gg=-gg;tt=-tt;
if min([aa, cc, gg, tt]) < 0:
    print("==="); quit()
s = list(s)
for i in range(len(s)):
    if s[i] == '?':
        if aa > 0:
            s[i] = 'A'; aa-=1;
        elif cc > 0:
            s[i] = 'C'; cc -= 1
        elif gg > 0:
            s[i] = 'G'; gg -= 1
        else:
            s[i] = 'T'; tt -= 1;
print(''.join(s))

def solve():
	n = int(input())
	if n % 4 != 0:
		print("===")
		return
	want = n // 4
	s = list(input())
	d = {'A' : 0, 'C' : 0, 'G' : 0, 'T' : 0}
	for c in s:
		if c in d:
			d[c] += 1
	for i in range(n):
		if s[i] == '?':
			for key in d:
				if d[key] < want:
					d[key] += 1
					s[i] = key
					break
	for key in d:
		if d[key] != want:
			print("===")
			return
	print(''.join(s))

solve()


def main():
    n = int(input())
    if n % 4 != 0:
        return 0
    s = input()
    d = dict()
    d["A"] = 0
    d["C"] = 0
    d["G"] = 0
    d["T"] = 0
    for i in s:
        if i in "ACGT":
            d[i] += 1
    app = ""
    for i in list(d.items()):
        if i[1] <= n // 4:
            app += i[0] * (n // 4 - i[1])
        else:
            return 0
    #print(s)
    #print(app)
    print(s.replace("?", "{}").format(*list(app)))
    return 1


if (not main()):
    print("===")



# python3

def solve():
    n = int(input())
    lis = list(input())
    if len(lis) % 4!=0:
        return "==="
    
    counter=[0,0,0,0]
    for j in lis:
        if j == "A":
            counter[0]+=1
        elif j == "C":
            counter[1]+=1
        elif j == "G":
            counter[2]+=1
        elif j == "T":
            counter[3]+=1

    avg = len(lis)/4
    for j in range(4):
        counter[j]-=avg
        if counter[j] > 0:
            return "==="

    for j in range(len(lis)):
        if lis[j]=="?":
            if counter[0] < 0:
                lis[j]="A"
                counter[0]+=1
            elif counter[1] < 0:
                lis[j]="C"
                counter[1]+=1
            elif counter[2] < 0:
                lis[j]="G"
                counter[2]+=1
            elif counter[3] < 0:
                lis[j]="T"
                counter[3]+=1
            
    return "".join(lis)
print(solve())


n = int(input())
s = input()


def solve(n, s):
	if n%4 > 0:
		return '==='
	for c in "ACGT":
		if 4*s.count(c) > n:
			return '==='
	r=''
	for c in "ACGT":
		r+= c*(n//4-s.count(c))

	j=0
	res = ''
	for c in s:
		if c == '?':
			res += r[j]
			j+=1
		else:
			res += c
	return res

print(solve(n, s))

n = int(input())
s = input()
if n % 4 != 0:
    print("===")
else:
    A = s.count("A")
    C = s.count("C")
    G = s.count("G")
    T = s.count("T")
    Q = s.count("?")
    #print(A, C, G, T, Q)
    #print(l)
    if max((A, C, G, T)) <= n//4:
        ns = ""
        for i in range(n):
            if s[i] == '?':
                if n//4-A>0:
                    ns += "A"
                    A+=1
                elif n//4-C>0:
                    ns += "C"
                    C+=1
                elif n//4-G>0:
                    ns += "G"
                    G+=1
                elif n//4-T>0:
                    ns += "T"
                    T+=1
            else:
                ns+=s[i]
        if "?" in ns:
            print("===")
        else:
            print(ns)
    else:
        print("===")


n = int(input())
genom = input()
A = n // 4 - genom.count("A")
С = n // 4 - genom.count("C")
G = n // 4 - genom.count("G")
T = n // 4 - genom.count("T")
if len(genom) % 4 != 0:
    print("===")
elif A < 0 or С < 0 or G < 0 or T < 0:
    print("===")
else:
    for i in genom:
        if i != "?":
            print(i, end="")
        else:
            if A > 0:
                print("A", end="")
                A -= 1
            elif С > 0:
                print("C", end="")
                С -= 1
            elif G > 0:
                print("G", end="")
                G -= 1
            elif T > 0:
                print("T", end="")
                T -= 1


n = int(input())
s = input()
if n%4 != 0:
    print("===")
else:
    sdict = dict()
    for i in 'ACGT?':
        sdict[i] = 0
    for i in s:
        sdict[i] +=1
    exitflag = False
    for i in 'ACGT':
        if sdict[i] > n/4:
            print("===")
            exitflag = True
            break
    if not exitflag:
        news = ""
        for i in s:
            if i != '?':
                news += i
            else:
                for j in 'ACGT':
                    if sdict[j] < n/4:
                        sdict[j]+=1
                        inputewith = j
                        break
                news += j
        print(news)


n = int(input())
st = input()

if n % 4 != 0:
    print('===')
else:
    ca, cb, cc, cd = 0, 0, 0, 0
    av = n // 4
    for i in range(len(st)):
        if st[i] == 'A':
            ca += 1
        elif st[i] == 'C':
            cb += 1
        elif st[i] == 'G':
            cc += 1
        elif st[i] == 'T':
            cd += 1

    if ca > av or cb > av or cc > av or cd > av:
        print('===')
    else:
        aa, ab, ac, ad = av - ca, av - cb, av - cc, av -cd
        ss = aa * 'A' + ab * 'C' + ac * 'G' + ad * 'T'
        cnt = 0
        for i in range(len(st)):
            if st[i] == '?':
                print(ss[cnt], end='')
                cnt += 1
            else:
                print(st[i], end='')
            
            


#!/usr/bin/env python3
def solve():
    _ = input()
    genom = list(input().strip())
    cntr = {"A": 0, "C": 0, "G": 0, "T": 0, "?": 0}
    for g in genom:
        cntr[g] += 1

    q = cntr["?"]
    del cntr["?"]

    maxval = max(cntr.values())
    needed = sum(maxval - val for val in list(cntr.values()))
    if needed > q:
        return "==="
    if (q - needed) % 4 != 0:
        return "==="
    maxval += (q - needed) // 4

    acgt = ("A", "C", "G", "T")

    for i in range(len(genom)):
        if genom[i] == "?":
            for g in acgt:
                if cntr[g] < maxval:
                    genom[i] = g
                    cntr[g] += 1
                    break

    return "".join(genom)


def __starting_point():
    print(solve())

__starting_point()

n = int(input())
x = n//4
s = input()
a = x - s.count('A')
c = x - s.count('C')
g = x - s.count('G')
t = x - s.count('T')
L = []
if n%4 != 0:
    print("===")
elif s.count('A') > x or s.count('C')>x or s.count('G') >x or s.count('T') > x:
    print("===")
else:
    for i in range(a):
        L.append('A')
    for i in range(c):
        L.append('C')
    for i in range(g):
        L.append('G')
    for i in range(t):
        L.append('T')
    s1 = ''
    j = 0
    for i in s:
        if i != '?':
            s1 += i
        elif i == '?':
            s1 += L[j]
            j +=1
    if s1.count('A') + s1.count('C')+s1.count('G')+s1.count('T') != n:
        print("===")
    else:
        print(s1)

#   Yergali B
n=int(input())
s=input()
k=n//4
aa,cc,gg,tt,t,ss=0,0,0,0,0,''
a=sorted(s)
for i in range(0,n):
    if a[i]=='?':
        t+=1
    elif a[i]=='A':
        aa+=1
    elif a[i]=='C':
        cc+=1
    elif a[i]=='G':
        gg+=1    
    elif a[i]=='T':
        tt+=1
if n%4!=0 or aa>k or cc>k or gg>k or tt>k:
    print('===')
else:
    for i in range(0,n):
        if s[i]!='?':
            ss+=s[i]
        else:
            if aa<k:
                ss+='A'
                aa+=1
            elif cc<k:
                ss+='C'
                cc+=1
            elif gg<k:
                ss+='G'
                gg+=1
            elif tt<k:
                ss+='T'
                tt+=1
    print(ss)


n=int(input())
s=input()
k=n//4
aa,cc,gg,tt,t,ss=0,0,0,0,0,''
a=sorted(s)
for i in range(0,n):
    if a[i]=='?':
        t+=1
    elif a[i]=='A':
        aa+=1
    elif a[i]=='C':
        cc+=1
    elif a[i]=='G':
        gg+=1    
    elif a[i]=='T':
        tt+=1
if n%4!=0 or aa>k or cc>k or gg>k or tt>k:
    print('===')
else:
    for i in range(0,n):
        if s[i]!='?':
            ss+=s[i]
        else:
            if aa<k:
                ss+='A'
                aa+=1
            elif cc<k:
                ss+='C'
                cc+=1
            elif gg<k:
                ss+='G'
                gg+=1
            elif tt<k:
                ss+='T'
                tt+=1
    print(ss)