Chef Ciel wants to put a fancy neon signboard over the entrance of her restaurant. She has not enough money to buy the new one so she bought some old neon signboard through the internet. Ciel was quite disappointed when she received her order - some of its letters were broken. But she realized that this is even better - she could replace each broken letter by any letter she wants. So she decided to do such a replacement that the resulting signboard will contain the word "CHEF" as many times as possible.
We can model the signboard as a string S having capital letters from 'A' to 'Z', inclusive, and question marks '?'. Letters in the string indicate the intact letters at the signboard, while question marks indicate broken letters. So Ciel will replace each question mark with some capital letter and her goal is to get the string that contains as many substrings equal to "CHEF" as possible. If there exist several such strings, she will choose the lexicographically smallest one.
Note 1. The string S = S1...SN has the substring "CHEF" if for some i we have SiSi+1Si+2Si+3 = "CHEF". The number of times "CHEF" is the substring of S is the number of those i for which SiSi+1Si+2Si+3 = "CHEF".
Note 2. The string A = A1...AN is called lexicographically smaller than the string B = B1...BN if there exists K from 1 to N, inclusive, such that Ai = Bi for i = 1, ..., K-1, and AK < BK. In particular, A is lexicographically smaller than B if A1 < B1. We compare capital letters by their positions in the English alphabet. So 'A' is the smallest letter, 'B' is the second smallest letter, ..., 'Z' is the largest letter.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The only line of each test case contains a string S.

-----Output-----
For each test case, output a single line containing the content of the signboard Chef Ciel will come up with. That is you should output the lexicographically smallest string that could be obtained from the input string by replacing all its question marks by some capital letters and having as many substrings equal to "CHEF" as possible.

-----Constraints-----
- 1 ≤ T ≤ 2013
- 1 ≤ length of S ≤ 2013
- Each character in S is either a capital letter from 'A' to 'Z', inclusive, or the question mark '?'.

-----Example-----
Input:
5
????CIELIS???E?
????CIELISOUR???F
T?KEITE?SY
????????
???C???

Output:
CHEFCIELISACHEF
CHEFCIELISOURCHEF
TAKEITEASY
CHEFCHEF
AAACHEF

-----Explanation -----
Example Case 1. Here the resulting string can have at most 2 substrings equal to "CHEF". For example, some possible such strings are:

- CHEFCIELISACHEF
- CHEFCIELISQCHEF
- CHEFCIELISZCHEF
However, lexicographically smallest one is the first one.

Example Case 3. Here the resulting string cannot have "CHEF" as its substring. Therefore, you must simply output the lexicographically smallest string that can be obtained from the given one by replacing question marks with capital letters.

Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Greedy algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
T = int(input())
for i in range(T):
	s = input()
	i = 0
	i = len(s)
	a = list(s)
	while i - 4 >= 0:
		if s[i - 4:i][0] in ['C', '?'] and s[i - 4:i][1] in ['H', '?'] and (s[i - 4:i][2] in ['E', '?']) and (s[i - 4:i][3] in ['F', '?']):
			a[i - 4] = 'C'
			a[i - 3] = 'H'
			a[i - 2] = 'E'
			a[i - 1] = 'F'
			i -= 4
		else:
			i -= 1
	for i in range(len(s)):
		if a[i] == '?':
			a[i] = 'A'
	for i in a:
		print(i, end='')
	print()


def can_replace(window):
	word = 'CHEF'
	for i in range(4):
		if window[i] == '?' or window[i] == word[i]:
			continue
		else:
			return False
	return True
for _ in range(int(input())):
	string = list(input().strip())
	N = len(string)
	for i in range(N - 4, -1, -1):
		window = string[i:i + 4]
		if can_replace(window):
			string[i:i + 4] = 'CHEF'
	for i in range(N):
		if string[i] == '?':
			string[i] = 'A'
	print(*string, sep='')


for _ in range(int(input())):
	arr = list(input())
	for i in range(len(arr) - 4, -1, -1):
		if arr[i] == 'C' or arr[i] == '?':
			if arr[i + 1] == 'H' or arr[i + 1] == '?':
				if arr[i + 2] == 'E' or arr[i + 2] == '?':
					if arr[i + 3] == 'F' or arr[i + 3] == '?':
						arr[i:i + 4] = ['C', 'H', 'E', 'F']
	for i in range(len(arr)):
		if arr[i] == '?':
			arr[i] = 'A'
	print(''.join(arr))


n = int(input())
while n:
	n = n - 1
	s = list(input())
	i = len(s) - 4
	while i >= 0:
		if (s[i] == 'C' or s[i] == '?') and (s[i + 1] == 'H' or s[i + 1] == '?') and (s[i + 2] == 'E' or s[i + 2] == '?') and (s[i + 3] == 'F' or s[i + 3] == '?'):
			s[i] = 'C'
			s[i + 1] = 'H'
			s[i + 2] = 'E'
			s[i + 3] = 'F'
			i = i - 4
		else:
			i = i - 1
	for i in range(len(s)):
		if s[i] == '?':
			s[i] = 'A'
	print(''.join(s))


for _ in range(int(input())):
	s = list(input())[::-1]
	l = len(s)
	i = 0
	while i < l:
		if i + 3 < l and (s[i] == 'F' or s[i] == '?') and (s[i + 1] == 'E' or s[i + 1] == '?') and (s[i + 2] == 'H' or s[i + 2] == '?') and (s[i + 3] == 'C' or s[i + 3] == '?'):
			(s[i + 3], s[i + 2], s[i + 1], s[i]) = ('C', 'H', 'E', 'F')
			i += 3
		elif s[i] == '?':
			s[i] = 'A'
		i += 1
	s.reverse()
	print(''.join(s))


for _ in range(int(input())):
	a = list(input())
	i = -1
	while i > 0 - (len(a) + 1):
		if a[i] == '?':
			try:
				if (a[i - 1] == '?' or a[i - 1] == 'E') and (a[i - 2] == '?' or a[i - 2] == 'H') and (a[i - 3] == '?' or a[i - 3] == 'C'):
					a[i] = 'F'
					a[i - 1] = 'E'
					a[i - 2] = 'H'
					a[i - 3] = 'C'
					i -= 3
			except:
				pass
		elif a[i] == 'C':
			try:
				if (a[i + 1] == '?' or a[i + 1] == 'H') and (a[i + 2] == '?' or a[i + 2] == 'E') and (a[i + 3] == '?' or a[i + 3] == 'F'):
					if i + 3 < 0:
						a[i + 1] = 'H'
						a[i + 2] = 'E'
						a[i + 3] = 'F'
			except:
				pass
		elif a[i] == 'H':
			try:
				if (a[i - 1] == '?' or a[i - 1] == 'C') and (a[i + 1] == '?' or a[i + 1] == 'E') and (a[i + 2] == '?' or a[i + 2] == 'F'):
					if i + 2 < 0:
						a[i - 1] = 'C'
						a[i + 1] = 'E'
						a[i + 2] = 'F'
						i -= 1
			except:
				pass
		elif a[i] == 'E':
			try:
				if (a[i - 2] == 'C' or a[i - 2] == '?') and (a[i - 1] == 'H' or a[i - 1] == '?') and (a[i + 1] == '?' or a[i + 1] == 'F'):
					if i + 1 < 0:
						a[i - 2] = 'C'
						a[i - 1] = 'H'
						a[i + 1] = 'F'
						i -= 2
			except:
				pass
		elif a[i] == 'F':
			try:
				if (a[i - 3] == 'C' or a[i - 3] == '?') and (a[i - 2] == 'H' or a[i - 2] == '?') and (a[i - 1] == 'E' or a[i - 1] == '?'):
					a[i - 3] = 'C'
					a[i - 2] = 'H'
					a[i - 1] = 'E'
					i -= 3
			except:
				pass
		i -= 1
	for i in range(len(a)):
		if a[i] == '?':
			print('A', end='')
		else:
			print(a[i], end='')
	print()


for _ in range(int(input())):
	W = list(input())
	for i in range(len(W) - 1, -1, -1):
		if W[i] == '?':
			if (i + 1 < len(W) and W[i + 1] == 'H') and (i + 2 < len(W) and W[i + 2] == 'E') and (i + 3 < len(W) and W[i + 3] == 'F'):
				W[i] = 'C'
			elif (i + 1 < len(W) and W[i + 1] == 'E') and (i + 2 < len(W) and W[i + 2] == 'F') and (i - 1 >= 0 and (W[i - 1] == 'C' or W[i - 1] == '?')):
				W[i] = 'H'
			elif (i + 1 < len(W) and W[i + 1] == 'F') and (i - 1 >= 0 and (W[i - 1] == 'H' or W[i - 1] == '?')) and (i - 2 >= 0 and (W[i - 2] == 'C' or W[i - 2] == '?')):
				W[i] = 'E'
			elif (i - 1 >= 0 and (W[i - 1] == 'E' or W[i - 1] == '?')) and (i - 2 >= 0 and (W[i - 2] == 'H' or W[i - 2] == '?')) and (i - 3 >= 0 and (W[i - 3] == 'C' or W[i - 3] == '?')):
				W[i] = 'F'
			else:
				W[i] = 'A'
	print(''.join(W))


def signboard(s):
	arr = []
	s = list(s)
	for i in range(len(s) - 4, -1, -1):
		if (s[i] == 'C' or s[i] == '?') and (s[i + 1] == 'H' or s[i + 1] == '?') and (s[i + 2] == 'E' or s[i + 2] == '?') and (s[i + 3] == 'F' or s[i + 3] == '?'):
			s[i] = 'C'
			s[i + 1] = 'H'
			s[i + 2] = 'E'
			s[i + 3] = 'F'
	for i in range(len(s)):
		if s[i] == '?':
			s[i] = 'A'
	return ''.join(s)
test = int(input())
for j in range(test):
	s = input()
	print(signboard(s))


T = int(input())
for t in range(T):
	S = list(input())
	for i in range(len(S) - 1, 2, -1):
		if S[i] in {'F', '?'}:
			if S[i - 1] in {'E', '?'}:
				if S[i - 2] in {'H', '?'}:
					if S[i - 3] in {'C', '?'}:
						S[i - 3:i + 1] = ['C', 'H', 'E', 'F']
	for i in range(len(S)):
		if S[i] == '?':
			S[i] = 'A'
	print(''.join(S))


test = int(input())
for _ in range(test):
	string = list(input())
	for i in range(len(string) - 4, -1, -1):
		if (string[i] == 'C' or string[i] == '?') and (string[i + 1] == 'H' or string[i + 1] == '?') and (string[i + 2] == 'E' or string[i + 2] == '?') and (string[i + 3] == 'F' or string[i + 3] == '?'):
			if string[i] == '?':
				string[i] = 'C'
			if string[i + 1] == '?':
				string[i + 1] = 'H'
			if string[i + 2] == '?':
				string[i + 2] = 'E'
			if string[i + 3] == '?':
				string[i + 3] = 'F'
	for i in range(len(string)):
		if string[i] == '?':
			string[i] = 'A'
	print(''.join(string))


possiblity = {'?EHC', '??H?', '?E??', '?EH?', 'F?H?', '???C', '?E?C', 'FE?C', 'F???', 'FE??', '????', 'FEH?', '??HC', 'F??C', 'F?HC'}
for _ in range(int(input())):
	st = input()
	st = st[::-1]
	ln = len(st)
	ans = ['0'] * ln
	i = ln - 1
	i = 0
	while i + 3 < ln:
		if st[i:i + 4] in possiblity:
			ans[i:i + 4] = ['F', 'E', 'H', 'C']
			i += 4
		else:
			ans[i] = st[i]
			i += 1
	if i < len(st):
		ans[i:] = st[i:]
	for i in range(ln):
		if ans[i] == '?':
			ans[i] = 'A'
	print(*ans[::-1], sep='')


def insertChef(text, i):
	if text[i] != 'C' and text[i] != '?':
		return
	if text[i + 1] != 'H' and text[i + 1] != '?':
		return
	if text[i + 2] != 'E' and text[i + 2] != '?':
		return
	if text[i + 3] != 'F' and text[i + 3] != '?':
		return
	text[i] = 'C'
	text[i + 1] = 'H'
	text[i + 2] = 'E'
	text[i + 3] = 'F'
TC = int(input())
for _ in range(TC):
	text = [c for c in input().strip()]
	for i in range(len(text) - 4, -1, -1):
		insertChef(text, i)
	for i in range(len(text)):
		if text[i] == '?':
			text[i] = 'A'
	print(''.join(text))


for _ in range(int(input())):
	s = list(input().strip())
	i = len(s) - 1
	while i >= 0:
		if i - 3 >= 0 and (s[i] == '?' or s[i] == 'F') and (s[i - 1] == '?' or s[i - 1] == 'E') and (s[i - 2] == '?' or s[i - 2] == 'H') and (s[i - 3] == '?' or s[i - 3] == 'C'):
			s[i] = 'F'
			s[i - 1] = 'E'
			s[i - 2] = 'H'
			s[i - 3] = 'C'
			i -= 4
		else:
			i -= 1
	pp = ''.join(s)
	pp = pp.replace('?', 'A')
	print(pp)


tests = int(input())

def check(a, b, c, d):
	return (a == '?' or a == 'C') and (b == '?' or b == 'H') and (c == '?' or c == 'E') and (d == '?' or d == 'F')
while tests:
	s = list(input())
	i = len(s) - 1
	while i >= 3:
		if check(s[i - 3], s[i - 2], s[i - 1], s[i]):
			s[i - 3] = 'C'
			s[i - 2] = 'H'
			s[i - 1] = 'E'
			s[i] = 'F'
		i -= 1
	for i in range(len(s)):
		if s[i] == '?':
			s[i] = 'A'
	print(''.join(s))
	tests -= 1


t = int(input())
while t > 0:
	a = list(input())
	n = len(a)
	l = ['????', '??E?', '?H??', '?HE?', '?H?F', '???F', '??EF', '?HEF', 'C???', 'C?E?', 'CH??', 'CHE?', 'CH?F', 'C??F', 'C?EF', 'CHEF']
	for i in range(16):
		l[i] = list(l[i])
	for i in range(n - 1, -1, -1):
		if i > 2:
			if a[i - 3:i + 1] in l:
				a[i - 3:i + 1] = ['C', 'H', 'E', 'F']
	for i in range(n):
		if a[i] == '?':
			a[i] = 'A'
	print(''.join(a))
	t -= 1


from sys import stdin, stdout
input = stdin.readline
t = int(input().strip())
for _ in range(t):
	s = input().strip()
	string = ['C', 'H', 'E', 'F']
	s = [ch for ch in s]
	n = len(s)
	count = 0
	d = {'C': [0, 3], 'H': [1, 2], 'E': [2, 1], 'F': [3, 0]}
	i = n - 1
	while i >= 0:
		if s[i] == '?':
			count += 1
			if count == 4:
				s[i:i + 4] = string
				count = 0
			i -= 1
		elif s[i] in string:
			count = 0
			(a, b) = d[s[i]]
			flag = 1
			sub = s[i - a:i + b + 1]
			if len(sub) != len(string):
				flag = 0
			else:
				for k in range(4):
					if sub[k] != '?' and sub[k] != string[k]:
						flag = 0
						break
			if flag:
				s[i - a:i + b + 1] = string
				i -= a + 1
			else:
				i -= 1
		else:
			count = 0
			i -= 1
	for i in range(n):
		if s[i] == '?':
			s[i] = 'A'
	s = ''.join(s)
	print(s)


def isPossible(l):
	if (l[0] == 'C' or l[0] == '?') and (l[1] == 'H' or l[1] == '?') and (l[2] == 'E' or l[2] == '?') and (l[3] == 'F' or l[3] == '?'):
		return True
	else:
		return False
T = int(input())
ans = []
for _ in range(T):
	S = list(input())
	N = len(S)
	for i in range(N - 1, 2, -1):
		if isPossible(S[i - 3:i + 1]):
			S[i] = 'F'
			S[i - 1] = 'E'
			S[i - 2] = 'H'
			S[i - 3] = 'C'
	for i in range(N):
		if S[i] == '?':
			S[i] = 'A'
	s = ''
	for i in S:
		s += i
	ans.append(s)
for i in ans:
	print(i)


for _ in range(int(input())):
	s = list(input())
	n = len(s)
	i = n - 1
	while i >= 3:
		f = s[i]
		e = s[i - 1]
		h = s[i - 2]
		c = s[i - 3]
		if (c == 'C' or c == '?') and (h == 'H' or h == '?') and (e == 'E' or e == '?') and (f == 'F' or f == '?'):
			if c == '?':
				s[i - 3] = 'C'
			if h == '?':
				s[i - 2] = 'H'
			if e == '?':
				s[i - 1] = 'E'
			if f == '?':
				s[i] = 'F'
			i -= 4
		elif s[i] == '?':
			s[i] = 'A'
			i -= 1
		else:
			i -= 1
	ans = ''
	for i in range(len(s)):
		if s[i] == '?':
			s[i] = 'A'
		ans += s[i]
	print(''.join(s))


def replace(j):
	if S[j] != '?' and S[j] != 'C' or (S[j + 1] != '?' and S[j + 1] != 'H') or (S[j + 2] != '?' and S[j + 2] != 'E') or (S[j + 3] != '?' and S[j + 3] != 'F'):
		return
	(S[j], S[j + 1], S[j + 2], S[j + 3]) = ('C', 'H', 'E', 'F')
for _ in range(int(input())):
	S = list(input())
	n = len(S)
	i = n - 4
	while i >= 0:
		replace(i)
		i -= 1
	for i in range(n):
		if S[i] == '?':
			S[i] = 'A'
	print(''.join(S))


t = int(input())
for i in range(t):
	s = input()
	final = ''
	count = 0
	list1 = ['CHE?', 'CH?F', 'C?EF', '?HEF', '?H?F', 'C?E?', '?HE?']
	list2 = ['CH??', 'C??F', '??EF', '?H??', '??E?']
	list3 = ['C???', '???F']
	list4 = ['????']
	len1 = len(s)
	rem_len = len1
	sub = ''
	last = ''
	while rem_len >= 4:
		start = rem_len - 4
		end = rem_len
		sub = s[start:end]
		if sub in list1 or sub in list2 or sub in list3 or (sub in list4):
			sub = 'CHEF'
			last = sub + last
			rem_len -= 4
		else:
			last = s[rem_len - 1:rem_len] + last
			rem_len -= 1
	last = s[:rem_len] + last
	last = last.replace('?', 'A')
	print(last)


t = int(input())
for _ in range(t):
	s = input()
	if len(s) < 4:
		for i in range(len(s)):
			if s[i] == '?':
				s = s[:i] + 'A' + s[i + 1:]
	else:
		for i in range(len(s) - 1, -1, -1):
			x = s[i - 3:i + 1]
			xx = 'CHEF'
			for j in range(len(x)):
				if x[j] == '?':
					x = x[:j] + xx[j] + x[j + 1:]
			if x == 'CHEF':
				s = s[:i - 3] + 'CHEF' + s[i + 1:]
		for i in range(len(s)):
			if s[i] == '?':
				s = s[:i] + 'A' + s[i + 1:]
	print(s)


for _ in range(int(input())):
	s = list(input())
	for i in range(len(s) - 4, -1, -1):
		if (s[i] == 'C' or s[i] == '?') and (s[i + 1] == 'H' or s[i + 1] == '?') and (s[i + 2] == 'E' or s[i + 2] == '?') and (s[i + 3] == 'F' or s[i + 3] == '?'):
			s[i] = 'C'
			s[i + 1] = 'H'
			s[i + 2] = 'E'
			s[i + 3] = 'F'
	s = str.join('', s)
	print(s.replace('?', 'A'))


from math import gcd
import sys
input = lambda : sys.stdin.readline().strip()
c = lambda x: 10 ** 9 if x == '?' else int(x)

def main():
	for _ in range(int(input())):
		s = list(input())[::-1]
		l = ['F', 'E', 'H', 'C']
		i = 0
		while i < len(s):
			if i + 3 < len(s):
				f = True
				for j in range(i, i + 4):
					if l[j - i] == s[j] or s[j] == '?':
						pass
					else:
						f = False
						break
				if f:
					for j in range(i, i + 4):
						s[j] = l[j - i]
				if s[i] == '?':
					s[i] = 'A'
			elif s[i] == '?':
				s[i] = 'A'
			i += 1
		print(*s[::-1], sep='')
main()


def solve():
	s = list(input())
	i = len(s) - 4
	while i >= 0:
		if (s[i] == '?' or s[i] == 'C') and (s[i + 1] == '?' or s[i + 1] == 'H') and (s[i + 2] == '?' or s[i + 2] == 'E') and (s[i + 3] == '?' or s[i + 3] == 'F'):
			s[i] = 'C'
			s[i + 1] = 'H'
			s[i + 2] = 'E'
			s[i + 3] = 'F'
			i = i - 4
		else:
			i = i - 1
	print(''.join(s).replace('?', 'A'))
t = int(input())
while t != 0:
	solve()
	t -= 1


no_of_test_cases = int(input())
given = 'CHEF'

def get_pos_for_chef(s, pos):
	possible = False
	for n in range(4):
		start = pos - n
		end = pos - n + 3
		if start < 0 or end >= len(s):
			continue
		for i in range(len(given)):
			if s[start + i] != given[i] and s[start + i] != '?':
				possible = False
				break
			possible = True
		if possible:
			return (start, end)
	return (-1, -1)

def get_mod_chef(s):
	for i in reversed(range(len(s))):
		if s[i] == '?':
			(start, end) = get_pos_for_chef(s, i)
			if start == -1:
				s = s[:i] + 'A' + s[i + 1:]
			else:
				s = s[:start] + 'CHEF' + s[end + 1:]
	return s
for i in range(no_of_test_cases):
	given_str = input()
	print(get_mod_chef(given_str))


t = int(input())
while t:
	s = list(input())
	n = len(s)
	i = n - 1
	while 3 <= i:
		d = s[i]
		c = s[i - 1]
		b = s[i - 2]
		a = s[i - 3]
		if (a == '?' or a == 'C') and (b == '?' or b == 'H') and (c == '?' or c == 'E') and (d == '?' or d == 'F'):
			if a == '?':
				s[i - 3] = 'C'
			if b == '?':
				s[i - 2] = 'H'
			if c == '?':
				s[i - 1] = 'E'
			if d == '?':
				s[i] = 'F'
			i -= 4
			continue
		elif d == '?':
			s[i] = 'A'
		i -= 1
	i = 0
	while i < n:
		if s[i] == '?':
			s[i] = 'A'
		i += 1
	print(''.join(s))
	t -= 1


def manychef(s):
	n = len(s)
	s = list(s)
	for i in range(n - 4, -1, -1):
		if s[i] != 'C' and s[i] != '?':
			continue
		if s[i + 1] != 'H' and s[i + 1] != '?':
			continue
		if s[i + 2] != 'E' and s[i + 2] != '?':
			continue
		if s[i + 3] != 'F' and s[i + 3] != '?':
			continue
		s[i] = 'C'
		s[i + 1] = 'H'
		s[i + 2] = 'E'
		s[i + 3] = 'F'
	for i in range(n - 1, -1, -1):
		if s[i] == '?':
			s[i] = 'A'
	return ''.join(s)
t = int(input())
for _ in range(t):
	s = input()
	print(manychef(s))


for _ in range(int(input())):
	s = list(input())
	i = len(s) - 1
	while i >= 0:
		if i - 3 >= 0 and (s[i] == '?' or s[i] == 'F') and (s[i - 1] == '?' or s[i - 1] == 'E') and (s[i - 2] == '?' or s[i - 2] == 'H') and (s[i - 3] == '?' or s[i - 3] == 'C'):
			s[i - 3:i + 1] = list('CHEF')
			i -= 4
			continue
		i -= 1
	print(''.join(s).replace('?', 'A'))


import copy

def already_filled(a, b, c, d):
	if a != '?' and b != '?' and (c != '?') and (d != '?'):
		return 1
	return 0

def can_be_corrected(a, b, c, d):
	if (a == 'C' or a == '?') and (b == 'H' or b == '?') and (c == 'E' or c == '?') and (d == 'F' or d == '?'):
		return 1
	return 0
t = int(input())
while t:
	string = list(input())
	i = len(string) - 4
	while i >= 0:
		if not already_filled(string[i], string[i + 1], string[i + 2], string[i + 3]):
			if can_be_corrected(string[i], string[i + 1], string[i + 2], string[i + 3]):
				string[i] = 'C'
				string[i + 1] = 'H'
				string[i + 2] = 'E'
				string[i + 3] = 'F'
				i -= 4
			else:
				if string[i + 3] == '?':
					string[i + 3] = 'A'
				i -= 1
		else:
			i -= 1
	for i in range(len(string)):
		if string[i] == '?':
			string[i] = 'A'
	print(''.join(string))
	t -= 1


for _ in range(int(input())):
	s = list(input())
	i = len(s) - 1
	while i >= 3:
		d = s[i]
		c = s[i - 1]
		b = s[i - 2]
		a = s[i - 3]
		if (a == 'C' or a == '?') and (b == 'H' or b == '?') and (c == 'E' or c == '?') and (d == 'F' or d == '?'):
			if a == '?':
				s[i - 3] = 'C'
			if b == '?':
				s[i - 2] = 'H'
			if c == '?':
				s[i - 1] = 'E'
			if d == '?':
				s[i] = 'F'
			i -= 4
			continue
		elif s[i] == '?':
			s[i] = 'A'
		i -= 1
	for x in range(len(s)):
		if s[x] == '?':
			s[x] = 'A'
	print(''.join(s))


def replace_if_possible(i):
	nonlocal string
	if string[i] != '?' and string[i] != 'C' or (string[i + 1] != '?' and string[i + 1] != 'H') or (string[i + 2] != '?' and string[i + 2] != 'E') or (string[i + 3] != '?' and string[i + 3] != 'F'):
		return
	string[i:i + 4] = 'CHEF'
t = int(input())
for _ in range(t):
	string = list(input())
	i = len(string) - 4
	while i >= 0:
		replace_if_possible(i)
		i -= 1
	for i in range(len(string)):
		if string[i] == '?':
			string[i] = 'A'
	print(''.join(string))


for _ in range(int(input())):
	string = list(input().strip())
	N = len(string)
	i = N - 4
	while i >= 0:
		if string[i] in '?C' and string[i + 1] in '?H' and (string[i + 2] in 'E?') and (string[i + 3] in '?F'):
			string[i] = 'C'
			string[i + 1] = 'H'
			string[i + 2] = 'E'
			string[i + 3] = 'F'
			i -= 4
		else:
			i -= 1
	print(''.join(string).replace('?', 'A'))


def check(arr):
	dic = {0: 'C', 1: 'H', 2: 'E', 3: 'F'}
	for i in range(4):
		if arr[i] != '?':
			if arr[i] != dic[i]:
				return -1
	for i in range(4):
		if arr[i] == '?':
			arr[i] = dic[i]
	return arr
t = int(input())
for _ in range(t):
	arr = input()
	arr = list(arr)
	i = len(arr)
	if i < 4:
		for k in range(i):
			if arr[k] == '?':
				arr[k] = 'A'
	while i > 3:
		if '?' in arr[i - 4:i]:
			if check(arr[i - 4:i]) == -1:
				i -= 1
				continue
			else:
				arr[i - 4:i] = check(arr[i - 4:i])
				i -= 3
		i -= 1
	for k in range(len(arr)):
		if arr[k] == '?':
			arr[k] = 'A'
	res = ''
	for ele in arr:
		res += ele
	print(res)


for x in range(int(input())):
	s = list(input())
	chef = [['C', '?'], ['H', '?'], ['E', '?'], ['F', '?']]
	ques = ['?']
	i = len(s) - 1
	for y in range(len(s)):
		if i < 0:
			break
		if i < 3:
			if s[i] != '?':
				pass
			else:
				s[i] = 'A'
			i -= 1
		else:
			d = s[i]
			c = s[i - 1]
			b = s[i - 2]
			a = s[i - 3]
			if a in chef[0] and b in chef[1] and (c in chef[2]) and (d in chef[3]):
				s[i] = 'F'
				s[i - 1] = 'E'
				s[i - 2] = 'H'
				s[i - 3] = 'C'
				i -= 4
			else:
				if s[i] == '?':
					s[i] = 'A'
				i -= 1
	print(''.join(s))


T = int(input())
for _ in range(T):
	S = list(input())
	for k in range(len(S)):
		if S[k] >= 'A' and S[k] <= 'Z' or S[k] == '?':
			continue
		else:
			print('-1')
	for i in range(len(S) - 4, -1, -1):
		if not (S[i] == 'C' or S[i] == '?'):
			continue
		if not (S[i + 1] == 'H' or S[i + 1] == '?'):
			continue
		if not (S[i + 2] == 'E' or S[i + 2] == '?'):
			continue
		if not (S[i + 3] == 'F' or S[i + 3] == '?'):
			continue
		S[i] = 'C'
		S[i + 1] = 'H'
		S[i + 2] = 'E'
		S[i + 3] = 'F'
	for i in range(len(S)):
		if S[i] == '?':
			S[i] = 'A'
	S = ''.join(S)
	print(S)


T = int(input())
for z in range(T):
	s = list(input())
	l = len(s)
	i = l - 4
	while i >= 0:
		if (s[i] == '?' or s[i] == 'C') and (s[i + 1] == '?' or s[i + 1] == 'H') and (s[i + 2] == '?' or s[i + 2] == 'E') and (s[i + 3] == '?' or s[i + 3] == 'F'):
			s[i] = 'C'
			s[i + 1] = 'H'
			s[i + 2] = 'E'
			s[i + 3] = 'F'
			i -= 4
		else:
			i -= 1
	print(''.join(s).replace('?', 'A'))


def possible_chef(signboard, i):
	if (signboard[i] == '?' or signboard[i] == 'C') and (signboard[i + 1] == '?' or signboard[i + 1] == 'H') and (signboard[i + 2] == '?' or signboard[i + 2] == 'E') and (signboard[i + 3] == '?' or signboard[i + 3] == 'F'):
		return True
	return False
for _ in range(int(input())):
	signboard = list(input())
	for i in range(len(signboard) - 4, -1, -1):
		if possible_chef(signboard, i):
			signboard[i] = 'C'
			signboard[i + 1] = 'H'
			signboard[i + 2] = 'E'
			signboard[i + 3] = 'F'
	for i in range(len(signboard)):
		if signboard[i] == '?':
			signboard[i] = 'A'
	print(''.join(signboard))


for _ in range(int(input())):
	s = input()
	n = len(s)

	def helper(i):
		return i - 3 >= 0 and (s[i] == 'F' or s[i] == '?') and (s[i - 1] == 'E' or s[i - 1] == '?') and (s[i - 2] == 'H' or s[i - 2] == '?') and (s[i - 3] == 'C' or s[i - 3] == '?')
	res = ''
	i = n - 1
	while i >= 0:
		if helper(i):
			res = 'CHEF' + res
			i -= 4
			continue
		res = (s[i] if s[i] != '?' else 'A') + res
		i -= 1
	print(res)


def check(s, ini):
	temp = 'CHEF'
	st = ini
	i = 3
	while i >= 0:
		C = s[st]
		T = temp[i]
		if C == T or C == '?':
			i -= 1
			st -= 1
		else:
			return False
	return True
a = int(input())
for i in range(a):
	d = list(input())
	end = len(d) - 1
	start = end - 3
	while start >= 0:
		if check(d, end):
			d[end] = 'F'
			d[end - 1] = 'E'
			d[end - 2] = 'H'
			d[end - 3] = 'C'
			end = end - 4
			start = start - 4
		else:
			end -= 1
			start -= 1
	for k in range(len(d)):
		if d[k] == '?':
			d[k] = 'A'
		print(d[k], end='')
	print()


def snek(a, l, r):
	s = 'CHEF'
	f = 0
	for i in range(len(s)):
		if not (a[l + i] == s[i] or a[l + i] == '?'):
			return False
	return True
t = int(input())
for i in range(t):
	s = list(input())
	l1 = len(s)
	r = len(s) - 1
	l = r - 3
	while l >= 0:
		if snek(s, l, r):
			s[l] = 'C'
			s[l + 1] = 'H'
			s[l + 2] = 'E'
			s[l + 3] = 'F'
		l -= 1
		r -= 1
	for j in range(l1 - 1, -1, -1):
		if s[j] == '?':
			s[j] = 'A'
	s = ''.join(s)
	print(s)


l = ['????', '?HEF', 'C?EF', 'CH?F', 'CHE?', '??EF', '?H?F', '?HE?', 'C??F', 'C?E?', 'CH??', '???F', '??E?', '?H??', 'C???', 'CHEF']
t = int(input())
for _ in range(t):
	s = input()
	n = len(s)
	temp = list(s)
	i = n
	while i - 4 >= 0:
		test = ''.join(temp[i - 4:i])
		if test not in l:
			i -= 1
		else:
			temp[i - 4:i] = ['C', 'H', 'E', 'F']
			i -= 4
	res = ''.join(temp)
	print(res.replace('?', 'A'))


for _ in range(int(input())):
	strr = list(input())
	tmp = ['????', '???F', '??E?', '??EF', '?H??', '?H?F', '?HE?', '?HEF', 'C???', 'C??F', 'C?E?', 'C?EF', 'CH??', 'CH?F', 'CHE?', 'CHEF']
	i = len(strr) - 1
	while i - 3 >= 0:
		dummy = ''.join(strr[i - 3:i + 1])
		if dummy in tmp:
			(strr[i - 3], strr[i - 2], strr[i - 1], strr[i]) = list('CHEF')
			i = i - 4
		elif strr[i] == '?':
			strr[i] = 'A'
			i -= 1
		else:
			i -= 1
	if i >= 0:
		for j in range(i + 1):
			if strr[j] == '?':
				strr[j] = 'A'
	print(''.join(strr))


T = int(input())
output = []
for _ in range(T):
	s = list(input())
	n = len(s)
	ends = set()
	for i in range(n):
		if s[i] in ['?', 'C'] and i < n - 3 and (s[i + 1] in ['?', 'H']) and (s[i + 2] in ['?', 'E']) and (s[i + 3] in ['?', 'F']):
			ends.add(i + 3)
		elif s[i] in ['?', 'H'] and 0 < i < n - 2 and (s[i - 1] in ['?', 'C']) and (s[i + 1] in ['?', 'E']) and (s[i + 2] in ['?', 'F']):
			ends.add(i + 2)
		elif s[i] in ['?', 'E'] and 1 < i < n - 1 and (s[i - 2] in ['?', 'C']) and (s[i - 1] in ['?', 'H']) and (s[i + 1] in ['?', 'F']):
			ends.add(i + 1)
		elif s[i] in ['?', 'F'] and 2 < i < n and (s[i - 3] in ['?', 'C']) and (s[i - 2] in ['?', 'H']) and (s[i - 1] in ['?', 'E']):
			ends.add(i)
	ends = list(ends)
	ends.sort()
	while len(ends) > 0:
		end = ends.pop()
		s[end - 3:end + 1] = ['C', 'H', 'E', 'F']
		while len(ends) > 0 and ends[-1] > end - 4:
			ends.pop()
	for i in range(n):
		if s[i] == '?':
			s[i] = 'A'
	output.append(''.join(s))
for o in output:
	print(o)


try:
	for _ in range(int(input())):
		s = list(input())
		l = len(s)
		i = l - 4
		while i >= 0:
			if (s[i] == '?' or s[i] == 'C') and (s[i + 1] == '?' or s[i + 1] == 'H') and (s[i + 2] == '?' or s[i + 2] == 'E') and (s[i + 3] == '?' or s[i + 3] == 'F'):
				s[i] = 'C'
				s[i + 1] = 'H'
				s[i + 2] = 'E'
				s[i + 3] = 'F'
				i -= 4
			else:
				i -= 1
		print(''.join(s).replace('?', 'A'))
except:
	pass


def chefCanBeFilled(list_s, i):
	if (list_s[i] == '?' or list_s[i] == 'C') and (list_s[i + 1] == '?' or list_s[i + 1] == 'H') and (list_s[i + 2] == '?' or list_s[i + 2] == 'E') and (list_s[i + 3] == '?' or list_s[i + 3] == 'F'):
		return True
	return False

def greedyChef(s):
	n = len(s)
	i = n - 4
	list_s = list(s)
	while i >= 0:
		if chefCanBeFilled(list_s, i):
			list_s[i] = 'C'
			list_s[i + 1] = 'H'
			list_s[i + 2] = 'E'
			list_s[i + 3] = 'F'
		i -= 1
	i = 0
	while i < n:
		if list_s[i] == '?':
			list_s[i] = 'A'
		i += 1
	return ''.join(list_s)
t = int(input())
for j in range(t):
	s = input()
	print(greedyChef(s))


d = int(input())
for k in range(d):
	str1 = input()
	str1 = list(str1)
	i = len(str1) - 4
	while i >= 0:
		if (str1[i] == 'C' or str1[i] == '?') and (str1[i + 1] == 'H' or str1[i + 1] == '?') and (str1[i + 2] == 'E' or str1[i + 2] == '?') and (str1[i + 3] == 'F' or str1[i + 3] == '?'):
			str1[i:i + 4] = list('CHEF')
			i -= 4
		else:
			i -= 1
	print(''.join(str1).replace('?', 'A'))


t = int(input())
for T in range(t):
	l = list(input())
	ind = len(l)
	ans = 0
	while ind > 3:
		val = l[ind - 4:ind]
		if val.count('?') == 0:
			ind -= 1
			continue
		s1 = ''.join(val)
		if s1 == 'CHEF':
			ind -= 4
			continue
		flag = 0
		if val.count('?') > 0:
			if val[0] != '?' and val[0] != 'C':
				flag = -1
			if val[0 + 1] != '?' and val[0 + 1] != 'H':
				flag = -1
			if val[0 + 2] != '?' and val[0 + 2] != 'E':
				flag = -1
			if val[0 + 3] != '?' and val[0 + 3] != 'F':
				flag = -1
		if flag == 0:
			l[ind - 4] = 'C'
			l[ind - 3] = 'H'
			l[ind - 2] = 'E'
			l[ind - 1] = 'F'
			ind -= 4
			continue
		ind -= 1
	n_string = ''.join(l)
	n_string = n_string.replace('?', 'A')
	print(n_string)


t = int(input())
for _t in range(t):
	S = list(input())
	n = len(S)
	for i in range(n - 1, -1, -1):
		if i >= 3 and (S[i - 3] in ('C', '?') and S[i - 2] in ('H', '?') and (S[i - 1] in ('E', '?')) and (S[i - 0] in ('F', '?'))):
			S[i - 3] = 'C'
			S[i - 2] = 'H'
			S[i - 1] = 'E'
			S[i - 0] = 'F'
	S = ''.join(S)
	S = S.replace('?', 'A')
	print(S)


def chef(s):
	string = list(s)
	length = len(string)
	if length < 4:
		for i in range(length):
			if string[i] == '?':
				string[i] = 'A'
		return ''.join(string)
	pos = length - 1
	while pos >= 3:
		if (string[pos] == '?' or string[pos] == 'F') and (string[pos - 1] == '?' or string[pos - 1] == 'E') and (string[pos - 2] == '?' or string[pos - 2] == 'H') and (string[pos - 3] == '?' or string[pos - 3] == 'C'):
			string[pos] = 'F'
			string[pos - 1] = 'E'
			string[pos - 2] = 'H'
			string[pos - 3] = 'C'
			pos -= 4
		else:
			pos -= 1
	for i in range(length):
		if string[i] == '?':
			string[i] = 'A'
	return ''.join(string)
try:
	t = int(input())
	while t:
		t -= 1
		s = input()
		ans = chef(s)
		print(ans)
except:
	pass


try:
	for _ in range(int(input())):
		S = list(input())
		chef = [['C', '?'], ['H', '?'], ['E', '?'], ['F', '?']]
		mark = ['?']
		i = len(S) - 1
		for _ in range(len(S)):
			if i < 0:
				break
			if i < 3:
				if S[i] != '?':
					pass
				else:
					S[i] = 'A'
				i -= 1
			else:
				d = S[i]
				c = S[i - 1]
				b = S[i - 2]
				a = S[i - 3]
				if a in chef[0] and b in chef[1] and (c in chef[2]) and (d in chef[3]):
					S[i] = 'F'
					S[i - 1] = 'E'
					S[i - 2] = 'H'
					S[i - 3] = 'C'
					i -= 4
				else:
					if S[i] == '?':
						S[i] = 'A'
					i -= 1
		print(''.join(S))
except:
	pass


import sys
from collections import Counter, defaultdict, deque
from math import gcd, sqrt, ceil

def li():
	return [int(i) for i in sys.stdin.readline().split()]

def si():
	return sys.stdin.readline().split()

def ii():
	return int(sys.stdin.readline())

def ip():
	return input()
for tastcas in range(int(input())):
	s = ip()
	n = len(s)
	a = [i for i in s]
	for i in range(n - 4, -1, -1):
		if (a[i] == '?' or a[i] == 'C') and (a[i + 1] == '?' or a[i + 1] == 'H') and (a[i + 2] == '?' or a[i + 2] == 'E') and (a[i + 3] == '?' or a[i + 3] == 'F'):
			a[i] = 'C'
			a[i + 1] = 'H'
			a[i + 2] = 'E'
			a[i + 3] = 'F'
	for i in range(n):
		if a[i] == '?':
			a[i] = 'A'
	for i in a:
		print(i, end='')
	print()


t = int(input())
for _ in range(t):
	list1 = list(input())
	n = len(list1)
	for i in range(n - 4, 0 - 1, -1):
		if (list1[i] == 'C' or list1[i] == '?') and (list1[i + 1] == 'H' or list1[i + 1] == '?') and (list1[i + 2] == 'E' or list1[i + 2] == '?') and (list1[i + 3] == 'F' or list1[i + 3] == '?'):
			if list1[i] == '?':
				list1[i] = 'C'
			if list1[i + 1] == '?':
				list1[i + 1] = 'H'
			if list1[i + 2] == '?':
				list1[i + 2] = 'E'
			if list1[i + 3] == '?':
				list1[i + 3] = 'F'
	for i in range(n):
		if list1[i] == '?':
			list1[i] = 'A'
	for val in list1:
		print(val, end='')
	print()


def check(arr, l, r):
	s = 'CHEF'
	flag = 0
	for i in range(len(s)):
		if not (arr[l + i] == s[i] or arr[l + i] == '?'):
			return False
	return True
n = int(input())
for _ in range(n):
	s = list(input())
	ln = len(s)
	r = len(s) - 1
	l = r - 3
	while l >= 0:
		if check(s, l, r):
			s[l] = 'C'
			s[l + 1] = 'H'
			s[l + 2] = 'E'
			s[l + 3] = 'F'
		l -= 1
		r -= 1
	for i in range(ln - 1, -1, -1):
		if s[i] == '?':
			s[i] = 'A'
	s = ''.join(s)
	print(s)


def checker(s, e, lst):
	a = lst[s]
	b = lst[s + 1]
	c = lst[s + 2]
	d = lst[s + 3]
	if (a == 'C' or a == '?') and (b == 'H' or b == '?') and (c == 'E' or c == '?') and (d == 'F' or d == '?'):
		lst[s] = 'C'
		lst[s + 1] = 'H'
		lst[s + 2] = 'E'
		lst[s + 3] = 'F'
t = int(input())
for _ in range(t):
	lst = list(input())
	n = len(lst)
	s = n - 4
	e = n - 1
	while s >= 0:
		checker(s, e, lst)
		s -= 1
		e -= 1
	for i in range(n):
		if lst[i] == '?':
			lst[i] = 'A'
	ans = ''.join(lst)
	print(ans)


def possible_chef(temp):
	chef = ['F', 'E', 'H', 'C']
	for j in range(len(temp)):
		if temp[j] == '?' or temp[j] == chef[j]:
			pass
		else:
			return False
			break
	return True
t = int(input())
chef = ['F', 'E', 'H', 'C']
for i in range(t):
	s = list(input())
	sr = s[::-1]
	j = 0
	while j < len(s):
		if j + 4 > len(s):
			while j < len(s):
				if sr[j] == '?':
					sr[j] = 'A'
				j += 1
		else:
			temp = sr[j:j + 4]
			ans = possible_chef(temp)
			if ans:
				for l in range(4):
					sr[j + l] = chef[l]
				j += 4
			elif sr[j] == '?':
				sr[j] = 'A'
				j += 1
			else:
				j += 1
	s = sr[::-1]
	for st in s:
		print(st, end='')
	print()


for i in range(int(input())):
	s = list(input())
	for i in range(len(s) - 4, -1, -1):
		c = 0
		if s[i] == '?':
			c += 1
		elif s[i] == 'C':
			c += 1
		else:
			continue
		if s[i + 1] == '?':
			c += 1
		elif s[i + 1] == 'H':
			c += 1
		else:
			continue
		if s[i + 2] == '?':
			c += 1
		elif s[i + 2] == 'E':
			c += 1
		else:
			continue
		if s[i + 3] == '?':
			c += 1
		elif s[i + 3] == 'F':
			c += 1
		else:
			continue
		if c == 4:
			s[i] = 'C'
			s[i + 1] = 'H'
			s[i + 2] = 'E'
			s[i + 3] = 'F'
	for j in range(len(s) - 1, -1, -1):
		if s[j] == '?':
			s[j] = 'A'
	print(*s, sep='')


for _ in range(int(input())):
	a = list(input())
	for i in reversed(range(len(a) - 3)):
		if (a[i] == 'C' or a[i] == '?') and (a[i + 1] == 'H' or a[i + 1] == '?') and (a[i + 2] == 'E' or a[i + 2] == '?') and (a[i + 3] == 'F' or a[i + 3] == '?'):
			a[i] = 'C'
			a[i + 1] = 'H'
			a[i + 2] = 'E'
			a[i + 3] = 'F'
	a = ''.join(a)
	a = a.replace('?', 'A')
	print(a)


tc = int(input())
for each in range(tc):
	str1 = str(input())
	str2 = str1[::-1]
	i = len(str1)
	word = 'CHEF'
	while i >= 4:
		temp = str1[i - 4:i]
		flag = 0
		for (j, each1) in enumerate(temp):
			if each1 != word[j] and each1 != '?':
				flag = 1
				break
		if flag == 0:
			if i == len(str1):
				str1 = str1[:i - 4] + 'CHEF'
			else:
				str1 = str1[:i - 4] + 'CHEF' + str1[i:]
			i -= 4
		else:
			i -= 1
	print(str1.replace('?', 'A'))


T = int(input())
while T > 0:
	S = list(input())
	for i in range(len(S) - 4, -1, -1):
		if not (S[i] == 'C' or S[i] == '?'):
			continue
		if not (S[i + 1] == 'H' or S[i + 1] == '?'):
			continue
		if not (S[i + 2] == 'E' or S[i + 2] == '?'):
			continue
		if not (S[i + 3] == 'F' or S[i + 3] == '?'):
			continue
		S[i] = 'C'
		S[i + 1] = 'H'
		S[i + 2] = 'E'
		S[i + 3] = 'F'
	for i in range(len(S)):
		if S[i] == '?':
			S[i] = 'A'
	print(''.join(S))
	T -= 1


t = int(input())
while t > 0:
	s = list(input())
	for i in range(len(s) - 1, 2, -1):
		if s[i] in {'F', '?'}:
			if s[i - 1] in {'E', '?'}:
				if s[i - 2] in {'H', '?'}:
					if s[i - 3] in {'C', '?'}:
						s[i - 3:i + 1] = ['C', 'H', 'E', 'F']
	for i in range(len(s)):
		if s[i] == '?':
			s[i] = 'A'
	print(''.join(s))
	t = t - 1