""" 想定解v3 別解 """ 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)-1,-1,-1): if splis[i] == spmax: lastc = S[i] elif S[i] == "?": S[i] = lastc print ("".join(S))