// Nachia くんだよ #include #include #include using namespace std; using ll = long long; using ull = unsigned long long; #define rep(i,n) for(int i=0; i<(n); i++) template struct RQ { int N; vector A; void mergev(int i){ if(i& a) : RQ(a.size()){ for(int i=0; i=1; i--) mergev(i); } void set(int p, S x){ p+=N; A[p] = x; for(int d=1; (1<>d); } S prod(int l, int r, int a=0, int b=0, int i=-1){ if(i==-1){ a=0; b=N; i=1; } if(r<=a || b<=l) return e(); if(l<=a && b<=r) return A[i]; S q1 = prod(l, r, a, (a+b)/2, i*2); S q2 = prod(l, r, (a+b)/2, b, i*2+1); return op(q1, q2); } // bool cmp(S) template int minleft(int r, E cmp, int a=0, int b=0, int i=-1){ static S x; if(i == -1){ a = 0; b = N; i = 1; x = e(); } if(r <= a) return a; if(b <= r){ S nx = op(A[i], x); if(cmp(nx)){ x = nx; return a; } } if(b-a == 1) return b; int q = minleft(r, cmp, (a+b)/2, b, i*2+1); if(q > (a+b)/2) return q; return minleft(r, cmp, a, (a+b)/2, i*2); } // bool cmp(S) template int maxright(int l, E cmp, int a=0, int b=0, int i=-1){ static S x; if(i == -1){ a = 0; b = N; i = 1; x = e(); } if(b <= l) return b; if(l <= a){ S nx = op(x, A[i]); if(cmp(nx)){ x = nx; return b; } } if(b-a == 1) return a; int q = maxright(l, cmp, a, (a+b)/2, i*2); if(q < (a+b)/2) return q; return maxright(l, cmp, (a+b)/2, b, i*2+1); } }; struct RQ2 { struct S{ int a; }; struct F{ int x; }; static S op(S l, S r){ return { min(l.a, r.a) }; } static S e(){ return { 1001001001 }; } static void mapping(F f, S& x){ x.a = min(f.x,x.a); } static void compose(F f, F& x){ x.x = min(f.x,x.x); } static F id(){ return { 1001001001 }; } struct Node{ S s; F f; }; int N; vector A; void mapf(int i, F f){ compose(f, A[i].f); mapping(f, A[i].s); } void mergev(int i){ if(i& a) : RQ2(a.size()){ for(int i=0; i=1; i--) mergev(i); } void set(int p, S x){ for(int d=1; (1<>d); p+=N; A[p].s = x; for(int d=1; (1<>d); } void apply(int l, int r, F x, int a=0, int b=0, int i=-1){ if(i==-1){ a=0; b=N; i=1; } if(r<=a || b<=l) return; if(l<=a && b<=r){ mapf(i, x); return; } spread(i); apply(l, r, x, a, (a+b)/2, i*2); apply(l, r, x, (a+b)/2, b, i*2+1); A[i].s = op(A[i*2].s, A[i*2+1].s); } S prod(int l, int r, int a=0, int b=0, int i=-1){ if(i==-1){ a=0; b=N; i=1; } if(r<=a || b<=l) return e(); if(l<=a && b<=r) return A[i].s; spread(i); S q1 = prod(l, r, a, (a+b)/2, i*2); S q2 = prod(l, r, (a+b)/2, b, i*2+1); return op(q1, q2); } // bool cmp(S) template int minleft(int r, E cmp, int a=0, int b=0, int i=-1){ static S x; if(i == -1){ a = 0; b = N; i = 1; x = e(); } if(r <= a) return a; if(b <= r){ S nx = op(A[i].s, x); if(cmp(nx)){ x = nx; return a; } } if(b-a == 1) return b; spread(i); int q = minleft(r, cmp, (a+b)/2, b, i*2+1); if(q > (a+b)/2) return q; return minleft(r, cmp, a, (a+b)/2, i*2); } // bool cmp(S) template int maxright(int l, E cmp, int a=0, int b=0, int i=-1){ static S x; if(i == -1){ a = 0; b = N; i = 1; x = e(); } if(b <= l) return b; if(l <= a){ S nx = op(x, A[i].s); if(cmp(nx)){ x = nx; return b; } } if(b-a == 1) return a; spread(i); int q = maxright(l, cmp, a, (a+b)/2, i*2); if(q < (a+b)/2) return q; return maxright(l, cmp, (a+b)/2, b, i*2+1); } }; int RmQe(){ return 1001001001; } int RmQop(int l,int r){ return min(l,r); } using RmQ = RQ2; //; int RMQe(){ return -1001001001; } int RMQop(int l,int r){ return max(l,r); } using RMQ = RQ; int main() { const int X = 200000; string S; cin >> S; int N = S.size(); RmQ ans(N); RMQ G(N); rep(i,N) if(S[i] != '?') G.set(i,S[i]*X+X-i-1); ans.apply(0,N,{(int)'z'}); ans.set(0,{(int)'z'}); while(G.prod(0,N) != 0){ int p = 0; while(true){ int x = G.prod(p,N); if(x == 0) break; int i = X - x % X - 1; int c = x / X; G.set(i,0); ans.apply(p,i,{c}); p = i; } ans.apply(p+1,N,{'a'}); } rep(i,N) if(S[i] == '?') S[i] = ans.prod(i,i+1).a; cout << S << "\n"; return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ ios::sync_with_stdio(false); cin.tie(nullptr); } } ios_do_not_sync_instance;