We have a string S of lowercase letters, and an integer array shifts.
Call the shift of a letter, the next letter in the alphabet, (wrapping around so that 'z' becomes 'a'). 
For example, shift('a') = 'b', shift('t') = 'u', and shift('z') = 'a'.
Now for each shifts[i] = x, we want to shift the first i+1 letters of S, x times.
Return the final string after all such shifts to S are applied.
Example 1:
Input: S = "abc", shifts = [3,5,9]
Output: "rpl"
Explanation: 
We start with "abc".
After shifting the first 1 letters of S by 3, we have "dbc".
After shifting the first 2 letters of S by 5, we have "igc".
After shifting the first 3 letters of S by 9, we have "rpl", the answer.

Note:

1 <= S.length = shifts.length <= 20000
0 <= shifts[i] <= 10 ^ 9

Difficulty: interview

Starter code:

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        

Solutions:
class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        # cumulative sum from back
        shifts[-1] = shifts[-1] % 26
        
        if len(shifts) >= 2:
            for i in range(len(shifts) - 2, -1, -1):
                shifts[i] += shifts[i + 1]
                shifts[i] = shifts[i] % 26
                
        # shift characters
        shifted_chars = []
        
        for i in range(len(S)):
            shifted_ascii = (ord(S[i]) - 97 + shifts[i]) % 26 + 97
            shifted_chars.append(chr(shifted_ascii))
            
        return \"\".join(shifted_chars)

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        tot = sum(shifts)
        ans = []
        for i in range(len(S)):
            ans.append(chr((ord(S[i]) - ord('a') + tot) % 26 + ord('a')))
            tot -= shifts[i]
        return ''.join(ans)

def caesarCipherEncryptor(string, key):
\tnewString = ''
\tfor i in string:
\t\tnewString += chr((ord(i) - ord('a') + key) % 26 + ord('a'))
\treturn newString

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        newString = \"\"
        l = len(S)
        
        for i in range(1, len(shifts), 1):
            shifts[l - 1 - i] += shifts[l - i]
        j = 0
        for i in S:
            newString += caesarCipherEncryptor(i, shifts[j])
            j += 1
            
        return newString
        

class Solution:
    CODE_Z = ord('z')
    
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        ret = ''
        self.calc_shift_times(shifts)
        for x in range(len(S)):
            ret += self.shift(S[x], shifts[x])
        
        return ret
      
    @classmethod
    def shift(cls, c, shift_times):
        ret = ord(c) + shift_times % 26
        if ret > cls.CODE_Z:
            ret -= 26
            
        return chr(ret)
    
    @staticmethod
    def calc_shift_times(shifts: List[int]):
        for x in range(-2, -(len(shifts) + 1), -1):
            shifts[x] += shifts[x+1]                     

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:      
        l = len(shifts)
        s = list(S)[:l]
        a = ord('a')
        
        # [1 + 3 + 5 + 7, 3 + 5 + 7, 5 + 7, 7]
        for i in range(1, len(shifts)):
            shifts[l - 1 - i] += shifts[l - i]
      
        print(shifts)
        
        for i in range(len(shifts)):
            # (ord(s[i]) - a + shifts[i]) % 26 이렇게 바꾼 숫자를 a에 더해줌
            s[i] = chr((ord(s[i]) - a + shifts[i]) % 26 + a)
        
        return ''.join(s)

class Solution:
    @staticmethod
    def shiftChar(c, shift):
        shift = shift % 26
        nc = ord(c)
        pos = nc - ord('a')
        if 25 - pos < shift:
            shift = -(26 - shift)
        return chr(nc + shift)

    def shiftingLetters(self, S: str, shifts) -> str:
        for i in range(len(shifts) - 2, -1, -1):
            shifts[i] += shifts[i + 1]
        return ''.join([Solution.shiftChar(c, shift) for c, shift in zip(S, shifts)])

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        
        
        t = \"\"
        s = sum(shifts)
        for i in range(len(shifts)):
            v = ord(S[i])+(s%26)
            let = None
            if v > 122:
                let = chr(v % 122 + 96)
            else: 
                let = chr(v)
            s -= shifts[i]
            t = t + let
        
        return t
            
            

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        add=0
        arr=list(S)
        i=len(S)-1
        while i>=0:
            add+=shifts[i]
            arr[i] = chr((((ord(arr[i]) - 97) + add) % 26) + 97)
            i-=1
        return ''.join(arr)

import string

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        if len(S) == 0:
            return ''
        
        # define alphabet mapping
        letters = string.ascii_lowercase
        num_letters = len(letters)
        
        # find the final positions of each letter before actually shifting
        final_shifts = [shift % num_letters for shift in shifts]
        
        running_shift = 0
        # start at the end so that we only have to go through list once
        for i, shift in enumerate(final_shifts[::-1]):
            index = len(final_shifts)-1-i
            # skip the \"last\"
            if index < len(final_shifts)-1:
                final_shifts[index] = (final_shifts[index] + running_shift) % num_letters
                # print('running_shift {} i {} running_shift {} shift {} value {}. {}'.format(
                #     running_shift, index, running_shift, shift, final_shifts[i], final_shifts))
            
            # accumulate going forward
            running_shift += shift
                    
        result = []
        for i, shift in enumerate(final_shifts):
            # find position of letter
            letter = S[i]
            # find position + shift
            position = (letters.index(letter) + shift) % num_letters
            shift_letter = letters[position]
            result.append(shift_letter)

        return ''.join(result)
    


class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        output = \"\"
        currShift = 0
        for i in range(len(S)-1, -1, -1):
            currShift += shifts[i]
            newPos = (self.getPosition(S[i]) + currShift)%26
            output = self.getLetter(newPos) + output
        return output
        
    def getPosition(self, char):
        return ord(char) - ord('a')
        
    def getLetter(self, position):
        return chr(ord('a') + position)
        
        

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        n = len(shifts)
        A = [0] * n
        
        def shifting(ch, k):
            return chr(((ord(ch) - 97 + k) % 26) + 97)
        
        A[-1] = shifts[-1]
        
        for i in range(n-2, -1, -1):
            A[i] = A[i+1] + shifts[i]
            
        return ''.join([shifting(c, A[i]) for i, c in enumerate(list(S))])
            
        
            
        


class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        cnt = 0
        acc_shifts = []
        
        for n in shifts[::-1]:
            cnt += n
            acc_shifts.append(cnt)
        
        acc_shifts = acc_shifts[::-1]
        
        new_s = []
        
        a_asc = ord('a')
        z_asc = ord('z')
        
        for i, n in enumerate(acc_shifts):
            new_ascii = ord(S[i]) + n
            new_ascii = a_asc + (new_ascii - a_asc) % 26
            new_s.append(chr(new_ascii))
        
        return ''.join(new_s)

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        def shift(s, n):
            curr = ord(s)-97
            curr = 97 + (curr+n)%26
            return chr(curr)
        S = list(S)
        shifts = shifts[::-1]
        for i in range(1, len(shifts)):
            shifts[i] += shifts[i-1]
        shifts = shifts[::-1]
        
        for i in range(len(shifts)):
            S[i] = shift(S[i], shifts[i])
        return ''.join(S)

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        a = ''
        cumshift = 0
        for pos in range(len(S)-1, -1, -1):
            sh = shifts[pos] % 26
            cumshift += sh
            cumshift = cumshift % 26
            ch = S[pos]
            #if (ch, cumshift) in cache:
            #    chn = cache.get((ch, cumshift))
            #else:
            chn = shift(ch, cumshift)
            #    cache[(ch, cumshift)] = chn
            a = chn + a
        return a
        
zval = 122 # ord('Z') if ch.isupper() else ord('z')
aval = 97 # ord('A') if ch.isupper() else ord('a')

def shift(ch, offset):
    offset = offset % 26
    och = ord(ch) 
    nch = och + offset
    if nch > zval:
        nch = aval + (nch - zval -1)
    return chr(nch)


class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        def shift(ch: str, n: int) -> str:
            print(ch, n)
            return chr((ord(ch) - ord('a') + n) % 26 + ord('a'))
        s = list(reversed(shifts))
        for i in range(1, len(s)):
            s[i] = s[i] + s[i - 1]
        res = [shift(ch, n) for ch, n in zip(S, reversed(s))]
        return \"\".join(res)

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        S_lst = list(S)
        plus = 0
        for i in range(len(shifts) - 1, -1, -1):
            plus += shifts[i]
            temp = ord(S_lst[i]) + plus % 26

            if temp > 122:
                temp = temp % 123 + 97
            S_lst[i] = chr(temp)

        return ''.join(S_lst)


class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        ln = len(shifts)
        new = [sum(shifts)]
        i = 0
        while i < ln-1:
            new.append(new[-1]-shifts[i])
            i += 1
        
        S = list(S)
        ans = ''
        for i,shift in enumerate(new):
            S[i] = chr(((ord(S[i]) - ord('a') + shift) % 26) + ord('a'))
            
        return ''.join(S)


class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        a = ''
        cumshift = 0
        for pos in range(len(S)-1, -1, -1):
            cumshift = (cumshift + shifts[pos]) % 26
            ch = S[pos]
            chn = shift(S[pos], cumshift)
            a = chn + a
        return a
        
def shift(ch, offset):
    #zval = 122 # ord('Z') if ch.isupper() else ord('z')
    #aval = 97 # ord('A') if ch.isupper() else ord('a')
    nch = ord(ch) + offset
    if nch > ord('z'):
        nch = ord('a') + (nch - ord('z') -1)
    return chr(nch)


class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        x = sum(shifts)
        ans = []
        for i, s in enumerate(S):
            idx = ord(s)- ord('a')
            ans.append(chr(ord('a')+(idx+x)%26))
            x-=shifts[i]
        return \"\".join(ans)
            

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        ans = []
        X = sum(shifts) % 26
        for i, c in enumerate(S):
            index = ord(c) - ord('a')
            ans.append(chr(ord('a') + (index + X) % 26))
            X = (X - shifts[i]) % 26
            
        return ''.join(ans)

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        n = len(shifts)
        ss = [0] * n
        ss[-1] = shifts[-1] % 26
        for i in range(n - 2, -1, -1):
            ss[i] = (shifts[i] + ss[i + 1]) % 26
        
        # ORD_a = 97
        # ORD_z = 122
        
        final_chars = [None] * n
        for i, ch in enumerate(S):
            _ord = ord(ch) + ss[i]
            if _ord > 122:
                _ord -= 26
            final_chars[i] = chr(_ord)
        
        return ''.join(final_chars)


class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        
#         def do(s, x):
#             return chr((ord(s)-ord('a')+x)%26+ord('a'))
        
#         S = list(S)
#         for i, x in enumerate(shifts):
#             for j, c in enumerate(S[:i+1]):
#                 S[j] = do(c, x)
#         return \"\".join(S)
        
        def do(s, x):
            return chr((ord(s)-ord('a')+x)%26+ord('a'))

        pre = []
        for s in shifts[::-1]:
            if(not pre):
                pre.append(s)
            else:
                pre.append(pre[-1]+s)
        
        S = list(S)
        for i in range(len(S)):
            S[i] = do(S[i], pre.pop())
        return \"\".join(S)

from collections import deque

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        offset = ord('a')
        wrap = 26
        current_shift = 0
        result = deque()
        for c, shift in reversed(list(zip(S, shifts))):
            current_shift = (current_shift + shift) % wrap
            after = chr(offset + (ord(c) + current_shift - offset) % wrap)
            result.append(after)
        return ''.join(reversed(result))

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        back_sum = [0] * len(shifts)
        N = 26
        back_sum = 0
        new_str = ''
        for i in range(len(S)-1, -1, -1):
            back_sum += shifts[i]
            new_str += chr((ord(S[i])-ord('a')+back_sum)%N+ord('a'))
        return new_str[::-1]

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        for i in range(len(shifts) - 2, -1, -1):
            shifts[i] += shifts[i + 1]
        
        res = [None] * len(S)
        for i in range(len(S)):
            res[i] = chr(((ord(S[i]) - ord(\"a\") + shifts[i]) % 26) + ord(\"a\"))
        return \"\".join(res)

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        s, ans = [0], []
        for n in reversed(shifts):
            s.append((s[-1] + n) % 26) 
        s = reversed(s[1:])
        
        for i, c in enumerate(S):
            n = chr((ord(c) - ord('a') + next(s)) % 26 + ord('a'))
            print(n)
            ans.append(n)
        return ''.join(ans)


class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        n, cumsum, res = len(S), 0, \"\"
        for i in range(n-1, -1, -1):
            cumsum += shifts[i]
            res = chr(ord('a') + (ord(S[i]) - ord('a') + cumsum) % 26) + res
        return res

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        S_lst = list(S)
        plus = 0
        for i in range(len(shifts) - 1, -1, -1):
            plus += shifts[i]
            temp = ord(S_lst[i]) + plus % 26

            if temp > ord('z'):
                temp = temp % (ord('z') + 1) + ord('a')
            S_lst[i] = chr(temp)

        return ''.join(S_lst)


def shift_char(char,num):

    idx = ord(char) - ord('a')
    idx = idx + num
    idx %= 26

    return chr(ord('a') + idx)

class Solution:
    
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        
        res = list(S)
        
        for i in range(len(shifts)-2,-1,-1):
            shifts[i] += shifts[i+1]
        
        for i in range(len(S)):
            res[i] = shift_char(res[i],shifts[i])
        
        return ''.join(res)

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        l = len(shifts)
        s = list(S)[:l]
        a = ord('a')
        for i in range(1, len(shifts), 1):
            shifts[l - 1 - i] += shifts[l - i]
        # print(shifts)
        for i in range(len(shifts)):
            s[i] = chr((ord(s[i]) - a + shifts[i]) % 26 + a)
        return ''.join(s)

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        nextS = shifts[0] % 26
        for i in range(len(S)):
            curr, nextS = nextS, shifts[i+1] % 26 if i < len(S) - 1 else 0
            shifts[0] += curr if i > 0 else 0
            if i < len(S) - 1:
                shifts[i+1] = -curr
        for i in range(len(S)):
            shifts[i] += shifts[i-1] if i > 0 else 0
        return ''.join([chr((ord(c) - 97 + s) % 26 + 97) for c, s in zip(S, shifts)])

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        suffix_sum_shifts = []
        suffix_sum = 0
        for shift in shifts[::-1]:
            suffix_sum += shift
            suffix_sum %= 26
            suffix_sum_shifts.append(suffix_sum)
        suffix_sum_shifts = suffix_sum_shifts[::-1]
        
        shifted_str = ''
        for i in range(len(S)):
            new_ord = (ord(S[i]) - ord('a') + suffix_sum_shifts[i]) % 26 + ord('a')
            shifted_str += chr(new_ord)
        return shifted_str
            


class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        if len(S) == 0:
            return \"\"
        
        sum_shifts = [sum(shifts)] * len(shifts)
        for i in range(1, len(shifts)):
            sum_shifts[i] = sum_shifts[i-1]-shifts[i-1]
        shifts = sum_shifts
        ret = []
        for i in range(len(S)):
            ret.append(chr(97+ (ord(S[i]) - 97 + shifts[i])%26))
            
        return \"\".join(ret)

import string
class Solution:
    def shiftingLetters(self, S, shifts):
        start = ord('a')
        res = []
        for i in reversed(range(len(shifts)-1)):
            shifts[i] += shifts[i+1]
        for i in range(len(S)):
            shifted = chr((ord(S[i]) - start + shifts[i]) % 26 + start)
            res.append(shifted)
        return ''.join(res)

# S[i] shifts sum(shifts[i:]) times. pre-compute the cummulative sum of shifts from right to left
#class Solution:
#    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
#        N = len(S)
#        cumsum = [0] * N
#        cumsum[-1] = shifts[-1]
#        for i in range(N-2,-1,-1):
#            cumsum[i] = cumsum[i+1] + shifts[i]
#        #print(cumsum)
#        res = []
#        for i in range(N):
#            c = S[i]
#            res.append(chr((ord(c) - ord('a') + cumsum[i]) % 26 + ord('a')))
#        return ''.join(res)

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        N = len(S)
        cumsum = [0] * N
        cumsum[-1] = shifts[-1] % 26
        for i in range(N-2,-1,-1):
            cumsum[i] = (cumsum[i+1] + shifts[i]) % 26
        #print(cumsum)
        res = []
        for i in range(N):
            c = S[i]
            res.append(chr((ord(c) - ord('a') + cumsum[i]) % 26 + ord('a')))
        return ''.join(res)

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        
        res = [None] * len(S)
        def shift(c, s):
            return chr(((ord(c) - ord(\"a\") + s) % 26) + ord(\"a\"))
        
        res[-1] = shift(S[-1], shifts[-1])
        for i in range(len(shifts) - 2, -1, -1):
            shifts[i] += shifts[i + 1]
            res[i] = shift(S[i], shifts[i])

        return \"\".join(res)

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        '''
        for pos, shift_offset in enumerate(shifts):
            n = ''
            for cp, ch in enumerate(S):
                if cp <= pos:
                    ch = shift(ch, shift_offset)
                n += ch
            S = n
        return S'''
        cache = {}
        a = ''
        cumshift = 0
        for pos in range(len(S)-1, -1, -1):
            sh = shifts[pos] % 26
            cumshift += sh
            cumshift = cumshift % 26
            ch = S[pos]
            if (ch, cumshift) in cache:
                chn = cache.get((ch, cumshift))
            else:
                chn = shift(ch, cumshift)
                cache[(ch, cumshift)] = chn
            a = chn + a
        return a
        '''    
        n = ''
        shifts = [s % 26 for s in shifts]
        for cp, ch in enumerate(S):
            offset = sum(shifts[cp:]) % 26
            if (ch, offset) in cache:
                chn = cache.get((ch, offset))
            else:
                chn = shift(ch, offset)
                cache[(ch, offset)] = chn
            n += chn
        return n
        '''
        
def shift(ch, offset):
    zval = 122 # ord('Z') if ch.isupper() else ord('z')
    aval = 97 # ord('A') if ch.isupper() else ord('a')
    offset = offset % 26
    och = ord(ch) 
    nch = och + offset
    if nch > zval:
        nch = aval + (nch - zval -1)
    return chr(nch)


import string
class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        letters = string.ascii_lowercase
        letter_to_idx = dict()
        for i, l in enumerate(letters):
            letter_to_idx[l] = i
        
        suffix = [sum(shifts)]
        for i in range(1, len(shifts)):
            suffix.append(suffix[-1]-shifts[i-1])
        
        res = ''
        for i, c in enumerate(S):
            res += letters[(letter_to_idx[c]+suffix[i])%26]
            
        return res

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        shifted_str = [None] * len(S)
        total_shifts = shifts[-1]
        shifted_str[-1] = self.shift_by_n(S[-1], total_shifts)
        for i in range(len(shifts)-2, -1, -1):
            total_shifts += shifts[i]
            shifted_str[i] = self.shift_by_n(S[i], total_shifts)
        return \"\".join(shifted_str)
        
   
    def shift_by_n(self, char: str, n: int) -> str:
        n = n % 26
        if ord(char) + n <= 122:
            shifted_char_position = ord(char) + n
            return chr(shifted_char_position)
        
        n = n - (122 - ord(char)) - 1           
        shifted_char_position = ord('a') + n
        return chr(shifted_char_position)
    
    
    

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
#         output = list(S)
#         if len(S) == 0 or len(S) != len(shifts): return output
#         alphabet = \"abcdefghijklmnopqrstuvwxyz\"
#         for i, k in enumerate(shifts):
#             # shifting logic and make dict
#             cipherString = alphabet[k%len(alphabet):] + alphabet[:k%len(alphabet)]
#             cipher = dict(zip(alphabet, cipherString))
#             for j in range(i + 1):
#                 # add to output
#                 output[j] = cipher[output[j]]
            
#         return ''.join(output)

        output = list(S)
        if len(S) == 0 or len(S) != len(shifts): return output
        alphabet = \"abcdefghijklmnopqrstuvwxyz\"
        shift = sum(shifts)
        for i, l in enumerate(S):
            cipherString = alphabet[shift%len(alphabet):] + alphabet[:shift%len(alphabet)]
            cipher = dict(zip(alphabet, cipherString))
            output[i] = cipher[l]
            shift -= shifts[i]
            
        return ''.join(output)
            
        

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        char = 'abcdefghijklmnopqrstuvwxyz'
        s = 0
        res = []
        for i in range(len(shifts)-1, -1, -1):
            s += shifts[i]
            res.insert(0, char[(char.index(S[i]) + s) % 26])
        return ''.join(res)

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        def shift(char, k):
            idx = ord(char) - ord('a')
            return chr(ord('a') + (idx + k) % 26)
        
        
        suffix = 0
        ans = []
        for i in range(len(shifts) - 1, -1, -1):
            suffix += shifts[i]
            ans.append(shift(S[i], suffix))
        return ''.join(ans[::-1])

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        suffix, N = [], len(S)
        for ii in range(N - 1, -1, -1):
            tmp = (shifts[ii] + (0 if (ii == N - 1) else suffix[0])) % 26
            suffix.insert(0, tmp)
        res = \"\"
        for ii, jj in zip(S, suffix):
            tmp = ord(ii) + jj
            if tmp > ord(\"z\"):
                tmp -= 26
            res += chr(tmp)
        return res

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        alphabets = 'abcdefghijklmnopqrstuvwxyz'
        n2s = {i: s for i, s in enumerate('abcdefghijklmnopqrstuvwxyz')}
        s2n = {s: i for i, s in list(n2s.items())}
        S_res = []
        assert len(S) == len(shifts)
        #for s, shift in zip(S, shifts):
        N = len(S)
        roll_over = 0
        for i in range(N):
            s = S[N - i - 1]
            shift = shifts[N - i - 1]
            roll_over = (shift + roll_over) % 26
            S_res.insert(0, n2s[(s2n[s] + roll_over) % 26])
        return ''.join(S_res)
        


class Solution:
    
    
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        new_shift = []
        si = 0
        for i in range(len(shifts)-1,-1,-1):
            si += shifts[i]
            new_shift.insert(0, si)
        
        ans = \"\"
        for i, s in enumerate(S):
            if ord(s) + new_shift[i] > ord('z'):
                ans += chr(ord('a')  + ((ord(s) -ord('a') + new_shift[i]) % 26))
            else:
                ans += chr(ord(s) + new_shift[i])
        return ans

class Solution:
    
    
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        new_shift = []
        
        si = 0
        for i in range(len(shifts)-1,-1,-1):
            si += shifts[i]
            new_shift.insert(0, si)
        
        ans = \"\"
        for i, s in enumerate(S):
            if ord(s) + new_shift[i] > ord('z'):
                ans += chr(ord('a')  + ((ord(s) -ord('a') + new_shift[i]) % 26))
            else:
                ans += chr(ord(s) + new_shift[i])
            
        return ans
        

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        '''
        for pos, shift_offset in enumerate(shifts):
            n = ''
            for cp, ch in enumerate(S):
                if cp <= pos:
                    ch = shift(ch, shift_offset)
                n += ch
            S = n
        return S'''
        cache = {}
        a = []
        cumshift = 0
        for pos in range(len(S)-1, -1, -1):
            sh = shifts[pos] % 26
            cumshift += sh
            cumshift = cumshift % 26
            ch = S[pos]
            if (ch, cumshift) in cache:
                chn = cache.get((ch, cumshift))
            else:
                chn = shift(ch, cumshift)
                cache[(ch, cumshift)] = chn
            a.insert(0, chn)
        return ''.join(a)
        '''    
        n = ''
        shifts = [s % 26 for s in shifts]
        for cp, ch in enumerate(S):
            offset = sum(shifts[cp:]) % 26
            if (ch, offset) in cache:
                chn = cache.get((ch, offset))
            else:
                chn = shift(ch, offset)
                cache[(ch, offset)] = chn
            n += chn
        return n
        '''
        
def shift(ch, offset):
    zval = 122 # ord('Z') if ch.isupper() else ord('z')
    aval = 97 # ord('A') if ch.isupper() else ord('a')
    offset = offset % 26
    och = ord(ch) 
    nch = och + offset
    if nch > zval:
        nch = aval + (nch - zval -1)
    return chr(nch)


class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        total_shifts = [0]
        for s in reversed(shifts):
            total_shifts = [s + total_shifts[0]] + total_shifts
            
        output = \"\"
        for c, shift in zip(S, total_shifts[:-1]):
            output += chr((ord(c) - ord('a') + shift) % 26 + ord('a'))
        return output
        

class Solution:
    def shiftingLetters(self, S: str, shift: List[int]) -> str:
        j = 1
        S = list(S)
        resTot = []
        for i in reversed(shift):
            if resTot:
                resTot = [resTot[0] + i] + resTot
            else:
                resTot = [i]
        #print(resTot)
        for i in range(len(resTot)):
            asci_val = ord(S[i]) + (resTot[i] % 26) - ord('a')
            S[i] = chr((asci_val % 26) + ord('a'))
        
        # for i in shifts:
        #     for k in range(j):
        #         asci_val = (ord(S[k]) + i - ord('a')) % 26
        #         S[k] = chr(asci_val + ord('a'))
        #     j += 1
        return \"\".join(S)

import string
class Solution:
    def shiftingLetters(self, S, shifts):
        start = ord('a')
        res = []
        shifter = lambda char, k: chr((ord(char) - start + k) % 26 + start)
        for i in reversed(range(len(shifts)-1)):
            shifts[i] += shifts[i+1]
        for i in range(len(S)):
            res.append(shifter(S[i], shifts[i]))
        return ''.join(res)

\"\"\"
    1. Problem Summary / Clarifications / TDD:

\"\"\"

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        
        s_len = len(S)
        
        for i in range(s_len - 2, -1, -1):
            shifts[i] += shifts[i + 1]
        
        new_s = []
        for i in range(s_len):
            new_s.append(chr(ord('a') + (ord(S[i]) - ord('a') + shifts[i])%26))
            
        return ''.join(new_s)
        

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        s = sum(shifts)
        n = 0
        a = []
        r = ''
        
        for i in shifts:
            a.append(s-n)
            n += i
            
        for i in range(len(a)):
            b = a[i] % (ord('z') - ord('a') + 1)
            c = ord(S[i]) + b
            if c > ord('z'):
                c = ord('a') + c - ord('z') - 1
            r += chr(c)
            
        return r

'''
180 + c + 

'''
class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        sol = \"\"
        cum = sum(shifts)
        for i in range(len(S)):
            if cum + ord(S[i]) > 122:
                ch = chr(((cum - (122 - ord(S[i]))) % 26) + 96)
                if ch == \"`\":
                    sol += \"z\"
                else:
                    sol += ch
            else:
                sol += chr(ord(S[i]) + cum)
            
            cum -= shifts[i]
        return sol