""" 想定誤解法 TLE 分割時にO(N^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: chflag = False #1つでも今回取るのがあった場合はTrueにする #nmax = -1 #今回取った最大の文字の番号 for i in range(len(S)): if S[i] != "?" and splis[i] == None: # and cd[S[i]] >= nmax: flag = True for j in range(i+1,len(S)): if splis[j] == None and cd[S[j]] > cd[S[i]]: flag = False break if flag: splis[i] = cnt chflag = True if not chflag: 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))