""" 誤解法想定 TLE ?を置き換える際にO(|S|^2) """ import bisect import sys alp = "abcdefghijklmnopqrstuvwxyz?" cd = {} #文字→数字にする辞書型 for i in range(-1,26): cd[alp[i]] = i #N = int(input()) S = list(input()) #制約チェック #assert N == len(S) for i in S: assert i in cd N = len(S) assert 1 <= N <= 10**5 #全て?の場合を処理する allq = True #全て?かどうかのフラグ for i in S: if i != "?": allq = False break if allq: print ("a"*N) sys.exit() #文字列を貪欲に分割する。 #後ろに、自分より辞書順で大きいのが無ければ取る cnt = 1 splis = [None] * N #何回目で取り除かれるか? while True: flag = False #1つでも今回取るのがあった場合はTrueにする nmax = -1 #今回取った最大の文字の番号 for i in range(len(S)-1,-1,-1): if S[i] != "?" and splis[i] == None and cd[S[i]] >= nmax: splis[i] = cnt nmax = cd[S[i]] flag = True if not flag: break cnt += 1 spmax = cnt - 1 #splisの最大値 #print (splis,spmax,file=sys.stderr) #lastc = "a" #splis[i]がspmaxと同じ文字で、最後に見た文字 for i in range(len(S)): if S[i] == "?": for j in range(i+1,len(S),1): if splis[j] == spmax: S[i] = S[j] break else: S[i] = "a" print ("".join(S))