#include <iostream>
#include <vector>
using namespace std;
 
string shiftingLetters(string s, vector<int>& shifts) {
    int n = s.length();
    vector<int> prefix(n);
 
 
    prefix[n - 1] = shifts[n - 1] % 26;
    for (int i = n - 2; i >= 0; i--) {
        prefix[i] = (prefix[i + 1] + shifts[i]) % 26;
    }
 
 
    for (int i = 0; i < n; i++) {
        int shifted = ((s[i] - 'a') + prefix[i]) % 26;
        s[i] = 'a' + shifted;
    }
 
    return s;
}
 
int main() {
    string s = "abc";
    vector<int> shifts = {3, 5, 9};
 
    string result = shiftingLetters(s, shifts);
    cout << "Shifted string: " << result << endl;
 
    return 0;
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKc3RyaW5nIHNoaWZ0aW5nTGV0dGVycyhzdHJpbmcgcywgdmVjdG9yPGludD4mIHNoaWZ0cykgewogICAgaW50IG4gPSBzLmxlbmd0aCgpOwogICAgdmVjdG9yPGludD4gcHJlZml4KG4pOwogICAgCiAKICAgIHByZWZpeFtuIC0gMV0gPSBzaGlmdHNbbiAtIDFdICUgMjY7CiAgICBmb3IgKGludCBpID0gbiAtIDI7IGkgPj0gMDsgaS0tKSB7CiAgICAgICAgcHJlZml4W2ldID0gKHByZWZpeFtpICsgMV0gKyBzaGlmdHNbaV0pICUgMjY7CiAgICB9CgoKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgaSsrKSB7CiAgICAgICAgaW50IHNoaWZ0ZWQgPSAoKHNbaV0gLSAnYScpICsgcHJlZml4W2ldKSAlIDI2OwogICAgICAgIHNbaV0gPSAnYScgKyBzaGlmdGVkOwogICAgfQoKICAgIHJldHVybiBzOwp9CgppbnQgbWFpbigpIHsKICAgIHN0cmluZyBzID0gImFiYyI7CiAgICB2ZWN0b3I8aW50PiBzaGlmdHMgPSB7MywgNSwgOX07CgogICAgc3RyaW5nIHJlc3VsdCA9IHNoaWZ0aW5nTGV0dGVycyhzLCBzaGlmdHMpOwogICAgY291dCA8PCAiU2hpZnRlZCBzdHJpbmc6ICIgPDwgcmVzdWx0IDw8IGVuZGw7CgogICAgcmV0dXJuIDA7Cn0K