Many Chefs

All submissions for this problem are available.
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 = S_{1}...S_{N} has the substring "CHEF" if for some i we have S_{i}S_{i+1}S_{i+2}S_{i+3} = "CHEF". The number of times "CHEF" is the substring of S is the number of those i for which S_{i}S_{i+1}S_{i+2}S_{i+3} = "CHEF".
Note 2. The string A = A_{1}...A_{N} is called lexicographically smaller than the string B = B_{1}...B_{N} if there exists K from 1 to N, inclusive, such that A_{i} = B_{i} for i = 1, ..., K1, and A_{K} < B_{K}. In particular, A is lexicographically smaller than B if A_{1} < B_{1}. 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.
Author:  laycurse 
Tester:  anton_lunyov 
Editorial  http://discuss.codechef.com/problems/MANYCHEF 
Tags  cook30, greedy, laycurse, simple 
Date Added:  2012013 
Time Limit:  2.013 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions