Alice and Bob continue their games with piles of stones. There are several stones arranged in a row, and each stone has an associated value which is an integer given in the array stoneValue.
Alice and Bob take turns, with Alice starting first. On each player's turn, that player can take 1, 2 or 3 stones from the first remaining stones in the row.
The score of each player is the sum of values of the stones taken. The score of each player is 0 initially.
The objective of the game is to end with the highest score, and the winner is the player with the highest score and there could be a tie. The game continues until all the stones have been taken.
Assume Alice and Bob play optimally.
Return "Alice" if Alice will win, "Bob" if Bob will win or "Tie" if they end the game with the same score.
 
Example 1:
Input: values = [1,2,3,7]
Output: "Bob"
Explanation: Alice will always lose. Her best move will be to take three piles and the score become 6. Now the score of Bob is 7 and Bob wins.

Example 2:
Input: values = [1,2,3,-9]
Output: "Alice"
Explanation: Alice must choose all the three piles at the first move to win and leave Bob with negative score.
If Alice chooses one pile her score will be 1 and the next move Bob's score becomes 5. The next move Alice will take the pile with value = -9 and lose.
If Alice chooses two piles her score will be 3 and the next move Bob's score becomes 3. The next move Alice will take the pile with value = -9 and also lose.
Remember that both play optimally so here Alice will choose the scenario that makes her win.

Example 3:
Input: values = [1,2,3,6]
Output: "Tie"
Explanation: Alice cannot win this game. She can end the game in a draw if she decided to choose all the first three piles, otherwise she will lose.

Example 4:
Input: values = [1,2,3,-1,-2,-3,7]
Output: "Alice"

Example 5:
Input: values = [-1,-2,-3]
Output: "Tie"

 
Constraints:

1 <= values.length <= 50000
-1000 <= values[i] <= 1000

Difficulty: interview

Starter code:

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        

Solutions:
class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        A = stoneValue
        dp = [0] * 3
        for i in range(len(A) - 1, -1, -1):
            dp[i % 3] = max(sum(A[i:i + k]) - dp[(i + k) % 3] for k in (1, 2, 3))
        
        if dp[0] > 0:
            return 'Alice'
        elif dp[0] < 0:
            return 'Bob'
        else:
            return 'Tie'


from itertools import accumulate
class Solution:
    def stoneGameIII(self, sv: List[int]) -> str:
        m = len(sv)
        dp = [-sys.maxsize] * m
        dp.append(0)
        ps = list(accumulate(sv))
        sm = sum(sv)

        for i in range(m-1, -1, -1):
            if i == m-1:
                dp[i] = sv[i]
            elif i == m-2:
                dp[i] = max(dp[i], sv[i] + (ps[-1] - ps[i] - dp[i+1]))
                dp[i] = max(dp[i], sv[i] + sv[i+1])
            else:
                dp[i] = max(dp[i], sv[i] + (ps[-1] - ps[i] - dp[i+1]))
                dp[i] = max(dp[i], sv[i] + sv[i+1] + (ps[-1] - ps[i+1] - dp[i+2]))
                dp[i] = max(dp[i], sv[i] + sv[i+1] + sv[i+2] + (ps[-1] - ps[i+2] - dp[i+3]))
        if dp[0] * 2 == sm:
            return 'Tie'
        if dp[0] * 2 > sm:
            return 'Alice'
        return 'Bob'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        dp = [0] * 3
        for i in range(len(stoneValue) - 1, -1, -1):
            dp[i % 3] = max(sum(stoneValue[i:i + k]) - dp[(i + k) % 3] for k in (1, 2, 3))
        if dp[0] == 0:
            return 'Tie'
        elif dp[0] > 0:
            return 'Alice'
        else:
            return 'Bob'


class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
#         cumsum = [0]*(n+1)
#         for i in range(1,n+1):
#             cumsum[i] = cumsum[i-1] + stoneValue[i-1]
        
#         @functools.lru_cache(None)
#         def helper(i, turn):
#             if turn == 0:
#                 if i == n:
#                     return 0
#                 if i == n-1:
#                     return stoneValue[-1]
#                 return max([cumsum[i+k]-cumsum[i] + helper(i+k,1) for k in [1,2,3] if i+k <= n])
#             else:
#                 if i == n:
#                     return 0
#                 if i == n-1:
#                     return 0
#                 return min([helper(i+k,0) for k in [1,2,3] if i+k <= n])
            
#         c = helper(0,0)
#         if c > sum(stoneValue) / 2.0:
#             return 'Alice'
#         elif c == sum(stoneValue) / 2.0:
#             return 'Tie'
#         else:
#             return 'Bob'
        A = stoneValue
        dp = [0] * 3
        for i in range(n - 1, -1, -1):
            dp[i % 3] = max(sum(A[i:i + k]) - dp[(i + k) % 3] for k in (1, 2, 3))
        c = dp[0]
        if c > 0:
            return 'Alice'
        elif c == 0:
            return 'Tie'
        else:
            return 'Bob'

class Solution:
    def stoneGameIII(self, arr: List[int]) -> str:
        ln, dp = len(arr), [float('-inf') for _ in range(len(arr))]
        dp.append(0)
        
        for i in range(ln-1, -1,-1):
            sm =0
            for j in range(i, min(ln, i+3)):
                sm +=arr[j]
                dp[i] = max(dp[i], sm - dp[j+1])
        if dp[0]>0:
            return 'Alice'
        elif dp[0]<0:
            return 'Bob'
        return 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        dp = [float('-inf')] * n # max score after i
        dp[-1] = stoneValue[-1]
        dp.append(0)
        for i in range(n-2, -1, -1):
            temp = 0
            for j in range(3):
                if i+j+1>n:
                    break
                temp += stoneValue[i+j]
                dp[i] = max(dp[i], temp-dp[i+j+1])
        if dp[0]>0:
            return 'Alice'
        elif dp[0]<0:
            return 'Bob'
        return 'Tie'


class Solution:
    def stoneGameIII(self, S: List[int]) -> str:
        
        n = len(S)
        
        dp = [0] * n
        
        for i in range(n)[::-1]:
            dp[i] =  max(sum(S[i:i+k]) - (dp[i+k] if i + k < n else 0) for k in (1,2,3)  )
            
        
        if dp[0] > 0:
            return 'Alice'
        elif dp[0] < 0:
            return 'Bob'
        else:
            return 'Tie'

class Solution:
    def stoneGameIII(self, nums: List[int]) -> str:
        n = len(nums)
        total = sum(nums)
        presum = [nums[-1]]
        if n > 1:
            presum.insert(0, nums[-2]+presum[0])
            nums[-2] = max(nums[-2], presum[0])
        if n > 2:
            presum.insert(0, nums[-3]+presum[0])
            nums[-3] = max([nums[-3] + presum[1] - nums[-2], nums[-3] + presum[1] - presum[2], presum[0]])
        for i in range(n-4, -1, -1):
            get_one = nums[i] + presum[0] - nums[i+1]
            get_two = nums[i] + presum[0] - presum[1] + presum[1] - nums[i+2]
            get_three = nums[i] + presum[0] - presum[2] + presum[2] - nums[i+3]
            presum.pop()
            presum.insert(0, presum[0] + nums[i])
            nums[i] = max([get_one, get_two, get_three])
        # print(nums)
        if nums[0] == presum[0]/2:
            return 'Tie'
        elif nums[0] > presum[0]/2:
            return 'Alice'
        return 'Bob'

class Solution:
    def stoneGameIII(self, stns: List[int]) -> str:
        stns.reverse()
        if len(stns)>1:
            ans = [0, stns[0], stns[1]+abs(stns[0])]
            for i in range(2, len(stns)):
                ans.append(max(stns[i]+stns[i-1]+stns[i-2]-ans[-3],
                               stns[i]+stns[i-1]-ans[-2],
                               stns[i]-ans[-1]))
        else:
            ans = stns
        return 'Alice' if ans[-1]>0 else 'Tie' if ans[-1]==0 else 'Bob'        

class Solution:
    def stoneGameIII(self, A: List[int]) -> str:
        n = len(A)
        dp = [-float('inf')]*n
        A.reverse()
        for i, x in enumerate(A):
            adding = 0
            for j in range(3):
                if i-j>=0:
                    adding += A[i-j]
                    dp[i] = max(dp[i], adding - (dp[i-j-1] if i-j>=1 else 0))
        if dp[-1] < 0:
            return 'Bob'
        return 'Tie' if dp[-1] == 0 else 'Alice'

from functools import lru_cache

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        psum = [0] * (n + 1)
        for i in range(n):
            psum[i + 1] = psum[i] + stoneValue[i]
            
        @lru_cache(None)
        def dp(start: int) -> int:
            if start >= n:
                return 0
            min_next = 2 ** 30
            for i in range(1, 4):
                min_next = min(min_next, dp(start + i))
            return psum[n] - psum[start] - min_next
        
        alice = dp(0)
        bob = psum[n] - alice
        return 'Alice' if alice > bob else 'Bob' if bob > alice else 'Tie'

class Solution:
    def stoneGameIII(self, A: List[int]) -> str:
        dp=[0]*3
        for i in range(len(A)-1,-1,-1):
            dp[i%3]=max(sum(A[i:i+k])-dp[(i+k)%3] for k in range(1,4))
        if dp[0]>0:
            return 'Alice'
        if dp[0]<0:
            return 'Bob'
        return 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        arr = stoneValue[:]
        dp = [0 for _ in range(3)]
        
        for i in range(len(arr)-1, -1, -1):
            dp[i%3] = max(sum(arr[i:i+k])- dp[(i+k)%3] for k in range(1, 4))
        return 'Alice' if dp[0] > 0 else 'Bob' if dp[0] <0 else 'Tie'


import math
from functools import lru_cache
class Solution:
    def stoneGameIII(self, stoneValue):
        n = len(stoneValue)
        @lru_cache(None)
        def solve(i):
            nonlocal stoneValue
            nonlocal n
            if i == n :
                return 0
            ans = -math.inf
            cursum = 0
            for j in range(i , i + 3):
                if j < n :
                    cursum += stoneValue[j]
                    ans = max(cursum - solve(j + 1) , ans)
            return ans

        ans = solve(0)
        if ans > 0 :
            return 'Alice'
        elif ans < 0 :
            return 'Bob'
        else:
            return 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        # aliceScore = [0]
        # bobScore = [0]
        # INVALID = 's'
        # def helper(stoneValues,index,aliceScore,bobScore,aliceTurn):
        #     scoreToUpdate = aliceScore
        #     if not aliceTurn:
        #         scoreToUpdate = bobScore
        #     if len(stoneValues) - 1 == index:
        #         scoreToUpdate[0] += stoneValues[index]
        #         return
        #     bck = scoreToUpdate[0]
        #     sums = []
        #     for i in range(1,4):
        #         scoreToUpdate[0] = bck
        #         if i + index <= len(stoneValues):
        #             for j in range(i):
        #                 scoreToUpdate[0] += stoneValues[index+j]
        #             helper(stoneValues,index + i,aliceScore,bobScore,not aliceTurn)
        #             sums.append(scoreToUpdate[0])
        #     if len(sums) > 0:
        #         scoreToUpdate[0] = max(sums)
        #     else:
        #         scoreToUpdate[0] = bck
        #     return
        # helper(stoneValue,0,aliceScore,bobScore,True)
        # if aliceScore[0] > bobScore[0]:
        #     return 'Alice'
        # elif bobScore[0] > aliceScore[0]:
        #     return 'Bob'
        # return 'Tie'
        mem = {}
        def helper(stoneValues,index):
            if index in mem:
                return mem[index]
            if index >= len(stoneValues):
                return 0
            ans = stoneValues[index] - helper(stoneValues,index+1)
            if index + 1 < len(stoneValues):
                temp = stoneValues[index] + stoneValues[index+1] - helper(stoneValues,index+2)
                ans = max(ans,temp)
            if index + 2 < len(stoneValues):
                temp = stoneValues[index] + stoneValues[index+1] + stoneValues[index+2] - helper(stoneValues,index+3)
                ans = max(ans,temp)
            mem[index] = ans
            return ans
        ans = helper(stoneValue,0)
        if ans > 0:
            return 'Alice'
        elif ans < 0:
            return 'Bob'
        return 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        N = len(stoneValue)
        F = [0] * (N + 1)
        S = [0] * (N + 1)

        for i in range(N - 1, -1, -1):
            max_val = -100000000
            for x in range(min(3, N - i)):
                val = sum(stoneValue[i:i + x + 1]) + S[i + x + 1]
                if max_val < val:
                    max_val = val
                    F[i] = val
                    S[i] = F[i + x + 1]
        
        if F[0] == S[0]:
            return 'Tie'
        return 'Alice' if F[0] > S[0] else 'Bob'


class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        # def pick(player, stones):
        #     if len(stones) == 0:
        #         return 0
        #     if player == 1:
        #         return max(
        #             [stones[0] + pick(2,stones[1:]), 
        #              sum(stones[:2]) + pick(2,stones[2:]), 
        #              sum(stones[:3]) + pick(2,stones[3:])
        #             ])
        #     else:
        #         return min(
        #             [-stones[0] + pick(1,stones[1:]), 
        #              -sum(stones[:2]) + pick(1,stones[2:]), 
        #              -sum(stones[:3]) + pick(1,stones[3:])
        #             ])
        # ans = pick(1,stoneValue)
        # if ans == 0:
        #     return 'Tie'
        # elif ans < 0:
        #     return 'Bob'
        # else:
        #     return 'Alice'
        dp = [0]*(len(stoneValue)+1)
        for i in range(len(stoneValue)-1,-1,-1):
            take = 0
            dp[i] = -float('inf')
            for k in range(3):
                if i+k >= len(stoneValue):
                    continue
                take += stoneValue[i+k]
                dp[i]= max(dp[i],take-dp[i+k+1])

        if dp[0] < 0: return 'Bob'
        if dp[0] > 0: return 'Alice'
        return 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        A=stoneValue
        N=len(A)
        MIN=-float('inf')
        dp=[0]*(N+1)
        
        for i in range(N-1, -1, -1):
            take=A[i]
            dp[i]=take-dp[i+1]
            if i+1<N:
                take+=A[i+1]
                dp[i]=max(dp[i], take-dp[i+2])
            if i+2<N:
                take+=A[i+2]
                dp[i]=max(dp[i], take-dp[i+3])
        if dp[0]==0:
            return 'Tie'
        return 'Alice' if dp[0]>0 else 'Bob'

class Solution:
    def stoneGameIII(self, stones: List[int]) -> str:
        rowlen=len(stones)
        i=rowlen-1
        i_1,i_2,i_3=0,0,0
        
        while i >= 0:
            
            answer=-float('inf')
            
            answer=max(answer,stones[i] - i_1)
            
            if i+1 < rowlen:
                answer=max(answer,stones[i]+stones[i+1] - i_2)  
                
            if i+2 < rowlen:
                answer=max(answer,stones[i]+stones[i+1]+stones[i+2] - i_3)
        
            i_3=i_2
            i_2=i_1
            i_1 = answer 
            i-=1
            
        if i_1 > 0:
            return 'Alice'
        elif i_1 < 0:
            return 'Bob'
        else:
            return 'Tie'


class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        postsum, dp = 0, [0]*(len(stoneValue)+3)
        for i in range(len(stoneValue)-1, -1, -1):
            postsum += stoneValue[i]
            dp[i] = postsum - min(dp[i+1], dp[i+2], dp[i+3])
        alice, bob = dp[0], postsum - dp[0]
        if alice == bob:
            return 'Tie'
        if alice > bob:
            return 'Alice'
        return 'Bob'

class Solution:
    def stoneGameIII(self, S: List[int]) -> str:
        
        n = len(S)
        
        dp = [0] * n
        
        for i in range(n)[::-1]:
            M = float('-inf')
            for k in range(1, 4):
                M = max(M, sum(S[i:i+k]) - (dp[i+k] if i + k < n else 0))
            dp[i] = M
        
        if dp[0] > 0:
            return 'Alice'
        elif dp[0] < 0:
            return 'Bob'
        else:
            return 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        stoneValue.insert(0, 0)
        # dp[i] means the max score we can get when i piles have been taken
        dp = [-sys.maxsize] * (n + 1)
        
        presum = [0] * (n + 1)
        for i in range(1, n + 1):
            presum[i] = presum[i - 1] + stoneValue[i]
        
        dp[n] = 0
        for i in reversed(range(n)):
            temp = 0
            for j in range(1, 4):
                if i + j > n:
                    break
                
                temp += stoneValue[i + j]
                dp[i] = max(dp[i], temp + presum[n] - presum[i + j] - dp[i + j])
        
        if dp[0] > presum[n] - dp[0]:
            return 'Alice'
        elif dp[0] < presum[n] - dp[0]:
            return 'Bob'
        else:
            return 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        length = len(stoneValue)
        dp = [0 for _ in range(length+1)]

        for i in range(length-1, -1, -1):
            take = 0
            dp[i] = -sys.maxsize
            for j in range(3):
                if i+j < length:
                    take += stoneValue[i+j]
                    dp[i] = max(dp[i], take - dp[i+j+1])

        # print(stoneValue)
        # print(dp)
        if dp[0] > 0:
            return 'Alice'
        elif dp[0] < 0:
            return 'Bob'
        else:
            return 'Tie'

class Solution:
    def stoneGameIII(self, stones: List[int]) -> str:
        
        rowlen=len(stones)
        index=0
        memo=[-1] * rowlen
             
        def helper(index,memo):
            
            if index >= rowlen:
                return 0
            elif memo[index] != -1:
                return memo[index] 
            else:
                answer=-float('inf')
                answer=max(answer,stones[index] - helper(index+1,memo))
                if index + 1 < rowlen:
                    answer=max(answer,stones[index]+stones[index+1] - helper(index+2,memo))
                
                if index + 2 < rowlen:
                    answer=max(answer,stones[index]+stones[index+1]+stones[index+2] - helper(index+3,memo))
                
                memo[index]=answer
                return memo[index]      
                
        answer=helper(0,memo)
        print(answer)
        
        if answer < 0:
            return 'Bob'
        elif answer > 0:
            return 'Alice'
        else:
            return 'Tie'

class Solution:
    def stoneGameIII(self, stones):
        total = sum(stones)
        alice_value = self._dfs(stones, 0, {})
        if alice_value > 0:
            return 'Alice'
        elif alice_value < 0:
            return 'Bob'
        return 'Tie'

    def _dfs(self, stones, start, memo):
        if start >= len(stones):
            return 0
        
        if start in memo:
            return memo[start]
        
        res = -2 ** 31
        curr_total = 0
        for i in range(start, min(start + 3, len(stones))):
            curr_total += stones[i]
            next_player_values = self._dfs(stones, i + 1, memo)
            
            res = max(
                res,
                curr_total - next_player_values,
            )
        
        memo[start] = res
        return res


class Solution:
    def stoneGameIII(self, cards):
        dp = [0]*3
        
        for i in range(len(cards)-1, -1, -1):
            dp[i%3] = max(sum(cards[i:i+k]) - dp[(i+k)%3] for k in [1,2,3])
        
        if dp[0] <0:
            return 'Bob'
        elif dp[0] >0:
            return 'Alice'
        else:
            return 'Tie'


def answer(x, y, alice, bob):
    if alice[x]>bob[y]:
        return 'Alice'
    elif alice[x]<bob[y]:
        return 'Bob'
    else:
        return 'Tie'


class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        if len(stoneValue)==1:
            if stoneValue[0]>0:
                return 'Alice'
            elif stoneValue[0]==0:
                return 'Tie'
            else:
                return 'Bob'
        alice = [0]*len(stoneValue)
        bob = [0]*len(stoneValue)
        alice[-1] = stoneValue[-1]
        bob[-1] = stoneValue[-1]
        
        cumSumm = [0]*len(stoneValue)
        summ = stoneValue[-1]
        cumSumm[-1] = summ
        for i in range(len(stoneValue)-2, -1, -1):
            summ+=stoneValue[i]
            cumSumm[i] = summ
            if i+2==len(stoneValue):
                alice[i] = max(stoneValue[i]+stoneValue[i+1], stoneValue[i]+cumSumm[i+1]-bob[i+1])
                bob[i] = max(stoneValue[i]+stoneValue[i+1], stoneValue[i]+cumSumm[i+1]-alice[i+1])
                continue
            if i+3==len(stoneValue):
                alice[i] = max(stoneValue[i]+cumSumm[i+1]-bob[i+1], stoneValue[i]+stoneValue[i+1]+cumSumm[i+2]-bob[i+2], stoneValue[i]+stoneValue[i+1]+stoneValue[i+2])
                bob[i] = max(stoneValue[i]+cumSumm[i+1]-alice[i+1], stoneValue[i]+stoneValue[i+1]+cumSumm[i+2]-alice[i+2], stoneValue[i]+stoneValue[i+1]+stoneValue[i+2])
                continue

            alice[i] = max(stoneValue[i]+cumSumm[i+1]-bob[i+1], stoneValue[i]+stoneValue[i+1]+cumSumm[i+2]-bob[i+2], stoneValue[i]+stoneValue[i+1]+stoneValue[i+2]+cumSumm[i+3]-bob[i+3])
            bob[i] = max(stoneValue[i]+cumSumm[i+1]-alice[i+1], stoneValue[i]+stoneValue[i+1]+cumSumm[i+2]-alice[i+2], stoneValue[i]+stoneValue[i+1]+stoneValue[i+2]+cumSumm[i+3]-alice[i+3])
            
            
        if len(stoneValue)==2:
            i = 0
            if alice[0]==stoneValue[i]+cumSumm[i+1]-bob[i+1]:
                x, y = i, i+1
            return answer(x, y, alice, bob)
        if len(stoneValue)==3:
            i = 0
            if alice[0]==stoneValue[i]+cumSumm[i+1]-bob[i+1]:
                x, y = i, i+1
            elif alice[0]==stoneValue[i]+stoneValue[i+1]+cumSumm[i+2]-bob[i+2]:
                x, y = i, i+2
            return answer(x, y, alice, bob)
        i = 0
        if alice[0]==stoneValue[i]+cumSumm[i+1]-bob[i+1]:
            x, y = i, i+1
        elif alice[0]==stoneValue[i]+stoneValue[i+1]+cumSumm[i+2]-bob[i+2]:
            x, y = i, i+2
        elif alice[0]==stoneValue[i]+stoneValue[i+1]+stoneValue[i+2]+cumSumm[i+3]-bob[i+3]:
            x, y = i, i+3
        return answer(x, y, alice, bob)
          


class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        self.mem = dict()
        self.n = len(stoneValue)
        self.values = stoneValue
        me, oppo = self.dfs(0)
        
        if me > oppo:
            return 'Alice'
        elif oppo > me:
            return 'Bob'
        return 'Tie'
        
        
    def dfs(self, idx):
        if idx >= self.n:
            return 0, 0
        if idx in self.mem:
            return self.mem[idx]
        
        oppo = 0
        rv = -float('inf')
        tmp = 0
        for i in range(idx, min(self.n, idx+3)):
            rv1, rv2 = self.dfs(i+1)
            tmp += self.values[i]
            if rv < tmp + rv2:
                rv = tmp + rv2
                oppo = rv1
                
        self.mem[idx] = rv, oppo
        return self.mem[idx]

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        
        prefix = [0] * (len(stoneValue) + 1)
        for i in range(len(stoneValue)):
            prefix[i+1] = prefix[i] + stoneValue[i]
            
        memo = {}
        aliceScore = self.dfs(stoneValue, 0, memo, prefix)
        
        total = sum(stoneValue)
        if total - aliceScore > aliceScore:
            return 'Bob'
        elif total - aliceScore < aliceScore:
            return 'Alice'
        return 'Tie'
    
    
    def dfs(self, stoneValue, i, memo, prefix):
        if i == len(stoneValue):
            return 0
        if i in memo:
            return memo[i]
        
        ans = stoneValue[i] + prefix[-1] - prefix[i+1] - self.dfs(stoneValue, i+1, memo, prefix)
        
        if i + 1 < len(stoneValue):
            ans = max(ans, stoneValue[i] + stoneValue[i+1] + prefix[-1] - prefix[i+2] - self.dfs(stoneValue, i+2, memo, prefix))
        if i + 2 < len(stoneValue):
            ans =  max(ans, stoneValue[i] + stoneValue[i+1] + stoneValue[i+2] + prefix[-1] - prefix[i+3] - self.dfs(stoneValue, i+3, memo, prefix))
            
        memo[i] = ans
        return memo[i]
        
        


class Solution:
    # Time: O(n * k), Space: O(n) - where k is number of maximum stones a player can pick
    def bottomUpDP(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        suffix_sum = [0 for _ in range(n + 1)]
        # dp[i] - maximum sum a player can accumulate he/she starts at position i
        dp = [0 for _ in range(n + 1)]
        
        for i in range(n - 1, -1, -1):
            suffix_sum[i] = stoneValue[i] + suffix_sum[i+1]
        
        for i in range(n - 1, -1, -1):
            player_pick_two_stones, player_pick_three_stones = float('-inf'), float('-inf')
            player_pick_one_stone = stoneValue[i] + suffix_sum[i + 1] - dp[i + 1]
            if i + 1 < n:
                player_pick_two_stones = stoneValue[i] + stoneValue[i + 1] + suffix_sum[i + 2] - dp[i + 2]
            if i + 2 < n:
                player_pick_three_stones = stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] + suffix_sum[i + 3] - dp[i + 3]
            dp[i] = max(player_pick_one_stone, player_pick_two_stones, player_pick_three_stones)
        
        if 2 * dp[0] == suffix_sum[0]:
            return 'Tie'
        elif 2 * dp[0] > suffix_sum[0]: # Alice score > Bob's score, dp[0] > suffix_sum[0] - dp[0]
            return 'Alice'
        else:
            return 'Bob'
    
    # top down solution using lru_cache
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        prefix = list(itertools.accumulate(stoneValue))
        
        @lru_cache(maxsize = None)
        def getScore(i):
            if i > len(stoneValue):
                return 0
            
            stones = float('-inf')
            for j in range(1, 3 + 1):
                prev = prefix[i - 1] if i - 1 >= 0 else 0
                stones = max(stones, prefix[-1] - prev - getScore(i + j))
            return stones
        
        alice_score = getScore(0)
        
        if alice_score > prefix[-1] - alice_score:
            return 'Alice'
        elif alice_score < prefix[-1] - alice_score:
            return 'Bob'
        else:
            return 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        length = len(stoneValue)
        
        @lru_cache(maxsize=None)
        def helper(current_idx):
            if current_idx >= length:
                return 0
            
            res = float('-inf')
            sum = 0
            
            for i in range(3):
                if current_idx + i < length:
                    sum += stoneValue[current_idx + i]
                    res = max(res, sum - helper(current_idx + i + 1))
            
            return res
        
        result = helper(0)
        
        if result == 0:
            return 'Tie'
        elif result > 0:
            return 'Alice'
        return 'Bob'


class Solution:
    def stoneGameIII(self, s: List[int]) -> str:
        
        cost = [-1]*(len(s))
        def helper(s, i):
            if i >= len(s):
                return 0
            if cost[i] != -1:
                return cost[i]
            
            ans = -sys.maxsize
            ans = max(ans, s[i] - helper(s, i+1))
            if i+1 < len(s):
                ans = max(ans, s[i]+s[i+1] - helper(s, i+2))
            if i+2 < len(s):
                ans = max(ans, s[i]+s[i+1]+s[i+2] - helper(s, i+3))
            cost[i] = ans
            return cost[i]
        
        a = helper(s, 0)
        if a > 0:
            return 'Alice'
        if a == 0:
            return 'Tie'
        return 'Bob'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        length = len(stoneValue)
        
        @lru_cache(maxsize=None)
        def helper(current_idx):
            if current_idx >= length:
                return 0
            
            res = float('-inf')
            sum = 0
            
            for i in range(3):
                if current_idx + i < length:
                    sum += stoneValue[current_idx + i]
                    res = max(res, sum - helper(current_idx + i + 1))
            
            return res
        
        result = helper(0)
        
        if result == 0:
            return 'Tie'
        elif result > 0:
            return 'Alice'
        return 'Bob'

class Solution:
    # Time: O(n * k), Space: O(n) - where k is number of maximum stones a player can pick
    def bottomUpDP(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        suffix_sum = [0 for _ in range(n + 1)]
        # dp[i] - maximum sum a player can accumulate he/she starts at position i
        dp = [0 for _ in range(n + 1)]
        
        for i in range(n - 1, -1, -1):
            suffix_sum[i] = stoneValue[i] + suffix_sum[i+1]
        
        for i in range(n - 1, -1, -1):
            player_pick_two_stones, player_pick_three_stones = float('-inf'), float('-inf')
            player_pick_one_stone = stoneValue[i] + suffix_sum[i + 1] - dp[i + 1]
            if i + 1 < n:
                player_pick_two_stones = stoneValue[i] + stoneValue[i + 1] + suffix_sum[i + 2] - dp[i + 2]
            if i + 2 < n:
                player_pick_three_stones = stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] + suffix_sum[i + 3] - dp[i + 3]
            dp[i] = max(player_pick_one_stone, player_pick_two_stones, player_pick_three_stones)
        
        if 2 * dp[0] == suffix_sum[0]:
            return 'Tie'
        elif 2 * dp[0] > suffix_sum[0]: # Alice score > Bob's score, dp[0] > suffix_sum[0] - dp[0]
            return 'Alice'
        else:
            return 'Bob'
        
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        prefix = list(itertools.accumulate(stoneValue))
        
        @lru_cache(maxsize = None)
        def getScore(i):
            if i > len(stoneValue):
                return 0
            
            stones = float('-inf')
            for j in range(1, 3 + 1):
                prev = prefix[i - 1] if i - 1 >= 0 else 0
                stones = max(stones, prefix[-1] - prev - getScore(i + j))
            return stones
        
        alice_score = getScore(0)
        
        if alice_score > prefix[-1] - alice_score:
            return 'Alice'
        elif alice_score < prefix[-1] - alice_score:
            return 'Bob'
        else:
            return 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        
        n = len(stoneValue)
        dp = [float('-inf')] * n
        dp[-1] = stoneValue[-1]
        for i in range(n - 2, -1, -1):
            s = 0
            for j in range(i, i + 3):
                s += stoneValue[j] if j < n else 0
                nxt = dp[j + 1] if j + 1 < n else 0
                dp[i] = max(dp[i], s - nxt)
        
                
                
#         @lru_cache(None)
#         def dp(cur):
#             if cur == len(stoneValue) - 1:
#                 return stoneValue[cur]
#             if cur >= len(stoneValue):
#                 return 0
#             ret = float('-inf')
#             s = 0
#             for i in range(3):
#                 nxt = dp(cur + i + 1)
#                 s += stoneValue[cur + i] if cur + i < len(stoneValue) else 0
#                 ret = max(ret, s - nxt)
#             return ret

#         ans = dp(0)
        ans = dp[0]
        if ans > 0:
            return 'Alice'
        elif ans < 0:
            return 'Bob'
        else:
            return 'Tie'

            


class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        memo = {}
        n = len(stoneValue)
        def solve(s):
            if s >= n: return 0
            elif s in memo :  return memo[s]
            currValue = 0
            best = -2**31
            for i in range(3):
                if s+i >= n:
                    break
                currValue += stoneValue[s+i]
                best = max(best, currValue - solve(s+i+1))
            memo[s] = best
            return best
        ans = solve(0)
        if ans > 0: return 'Alice'
        elif ans < 0 : return 'Bob'
        else: return 'Tie'

class Solution:
#     # Time: O(n * k), Space: O(n) - where k is number of maximum stones a player can pick
#     def stoneGameIII(self, stoneValue: List[int]) -> str:
#         n = len(stoneValue)
#         suffix_sum = [0 for _ in range(n + 1)]
#         # dp[i] - maximum sum a player can accumulate he/she starts at position i
#         dp = [0 for _ in range(n + 1)]
        
#         for i in range(n - 1, -1, -1):
#             suffix_sum[i] = stoneValue[i] + suffix_sum[i+1]
        
#         for i in range(n - 1, -1, -1):
#             player_pick_two_stones, player_pick_three_stones = float('-inf'), float('-inf')
#             player_pick_one_stone = stoneValue[i] + suffix_sum[i + 1] - dp[i + 1]
#             if i + 1 < n:
#                 player_pick_two_stones = stoneValue[i] + stoneValue[i + 1] + suffix_sum[i + 2] - dp[i + 2]
#             if i + 2 < n:
#                 player_pick_three_stones = stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] + suffix_sum[i + 3] - dp[i + 3]
#             dp[i] = max(player_pick_one_stone, player_pick_two_stones, player_pick_three_stones)
        
#         if 2 * dp[0] == suffix_sum[0]:
#             return 'Tie'
#         elif 2 * dp[0] > suffix_sum[0]: # Alice score > Bob's score, dp[0] > suffix_sum[0] - dp[0]
#             return 'Alice'
#         else:
#             return 'Bob'
        
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        prefix = list(itertools.accumulate(stoneValue))
        
        @lru_cache(maxsize = None)
        def getScore(i):
            if i > len(stoneValue):
                return 0
            
            stones = float('-inf')
            
            for j in range(1, 3 + 1):
                prev = prefix[i - 1] if i - 1 >= 0 else 0
                stones = max(stones, prefix[-1] - prev - getScore(i + j))
            return stones
        
        alice_score = getScore(0)
        
        if alice_score > prefix[-1] - alice_score:
            return 'Alice'
        elif alice_score < prefix[-1] - alice_score:
            return 'Bob'
        else:
            return 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        # Get the highest socre of Alice s1, 
        # then score of Bob is sum(stoneValue) - s.
        # If s1 > s2 => Alice, if s1 == s2 => Tie, else
        # Bob
        
        # [1,2,3,6]
        # TLE, because in getScore we have to sum(stoneValue) since we 
        # don't need to get the explict score, we can optimize it, which
        # is the second approach.
#         memo = {}
#         def getScore(start):
#             if start >= len(stoneValue):
#                 return 0
#             if start in memo:
#                 return memo[start]
#             res = -math.inf
#             front = 0
#             behind = sum(stoneValue[start:])
#             for i in range(start, min(start+3, len(stoneValue))):
#                 front += stoneValue[i]
#                 behind -= stoneValue[i]
#                 cur = front + behind - getScore(i+1)
#                 res = max(cur, res)
            
#             return res
                
#         s1 = getScore(0)
#         s2 = sum(stoneValue) - s1
        
#         if s1 > s2:
#             return 'Alice'
#         elif s1 == s2:
#             return 'Tie'
#         else:
#             return 'Bob'
        
        # Second approach
        memo = {}
        def dfs(start):
            if start >= len(stoneValue):
                return 0
            if start in memo:
                return memo[start]
            memo[start] = -math.inf
            score = 0
            for i in range(start, min(len(stoneValue), start+3)):
                score += stoneValue[i]
                memo[start] = max(memo[start], score - dfs(i+1))
            
            return memo[start]
        score = dfs(0)
        
        if score > 0:
            return 'Alice'
        elif score == 0:
            return 'Tie'
        else:
            return 'Bob'

class Solution:
    def stoneGameIII(self, sv: List[int]) -> str:
        n=len(sv)
        sv+=[0,0]
        dp=[0 for _ in range(n+3)]
        for i in range(n-1,-1,-1):
            dp[i]=max(sv[i]-dp[i+1],sv[i]+sv[i+1]-dp[i+2], sv[i]+sv[i+1]+sv[i+2]-dp[i+3])
        if dp[0]>0:
            return 'Alice'
        elif dp[0]<0:
            return 'Bob'
        return 'Tie'

                
                


class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        @lru_cache(None)
        def dp(cur):
            if cur == len(stoneValue) - 1:
                return stoneValue[cur]
            if cur >= len(stoneValue):
                return 0
            ret = float('-inf')
            s = 0
            for i in range(3):
                # if cur + i + 1 >= len(stoneValue):
                #     break
                nxt = dp(cur + i + 1)
                s += stoneValue[cur + i] if cur + i < len(stoneValue) else 0
                ret = max(ret, s - nxt)
            # print(cur, ret)
            return ret

        ans = dp(0)
        if ans > 0:
            return 'Alice'
        elif ans < 0:
            return 'Bob'
        else:
            return 'Tie'

            


class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        # 采用和类似于stoneGameII的方法，可以吗？
        # 残局
        # solve(s) score diff
        # M=1,2,3
        # x=[1,2,3]
        # solve(s) = max(sum(sv[s:s+x-1]) - solve(s+x))
        
        n = len(stoneValue)
        
        cache = dict() # s:score
        
        def solve(s):
            if s>=n: return 0
            
            if s in cache: return cache[s]
            
            best = -2**31
            presum = 0
            
            for x in range(1, 4):
                if s+x-1 >= n:
                    break
                presum += stoneValue[s+x-1]
                best = max(best, presum - solve(s+x))
            cache[s] = best
            return best
        score = solve(0)
        return 'Alice' if score > 0 else 'Bob' if score < 0 else 'Tie'

from functools import lru_cache

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        vals = stoneValue
        n = len(vals)
        dp = collections.deque([None] * 3)
        dp[0] = [0, 0]
        
        for i in range(n - 1, -1, -1):
            p1, p2 = -1e9, -1
            s = 0
            for j in range(i, min(i + 3, n)):
                s += vals[j]
                p1_, p2_ = dp[j - i]
                p2_ += s
                if p2_ > p1:
                    p1 = p2_
                    p2 = p1_
            dp.pop()
            dp.appendleft((p1, p2))
        
        p1, p2 = dp[0]
        # print(p1, p2)
        # p2 = sum(vals) - p1
        if p1 > p2:
            return 'Alice'
        elif p1 == p2:
            return 'Tie'
        return 'Bob'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        # take 1, 2, or 3 stones from the first remaining stones of the row
        
        # memorized dp, with mimmax process
        
        # state = dp[s], start from index s
        
        # take one, stoneValue[s] - dp[s+1]
        # take two, stoneValue[s,s+1] - dp[s+2]
        # take three, stoneValue[s, s+1, s+2] - dp[s+3]
        # max value of these three branches
        
        # dp[s] > 0
        
        memo = {}
        n = len(stoneValue)
        
        def dp(s):
            if s>=n: return 0
            if s in memo:
                return memo[s]
            
            ans = -2**31
            for i in range(1, 4):
                if s + i > n: # was bad, s+i>=n was not correct!
                    break
                ans = max(ans, sum(stoneValue[s:s+i]) - dp(s+i))
            memo[s] = ans
            return ans
        
        score = dp(0) - sum(stoneValue)/2
        #print(score, sum(stoneValue)/2)
        return 'Alice' if score > 0 else 'Bob' if score < 0 else 'Tie'
        
    def stoneGameIII(self, stoneValue: List[int]) -> str:       
        # 采用和类似于stoneGameII的方法，可以吗？-> works!! great 太好了，get一个minmax的求解的模板！！！
        # 残局
        # solve(s) score diff
        # M=1,2,3
        # x=[1,2,3]
        # solve(s) = max(sum(sv[s:s+x-1]) - solve(s+x))
        
        n = len(stoneValue)
        
        cache = dict() # s:score
        
        def solve(s):
            if s>=n: return 0
            if s in cache: return cache[s]
            
            best = -2**31
            presum = 0
            
            for x in range(1, 4):
                if s+x-1 >= n:
                    break
                presum += stoneValue[s+x-1]
                best = max(best, presum - solve(s+x))
            cache[s] = best
            return best
        score = solve(0)
        return 'Alice' if score > 0 else 'Bob' if score < 0 else 'Tie'

class Solution:
    
    def stoneGameIII(self, stones):
        # only allow to take from the head, 1,2,3
        
        # recursive dp method
        memo = dict()
        n = len(stones)
        def dp(s):
            if s == n: return 0
            if s in memo: return memo[s]
            
            ans = -2**31
            
            presum = 0
            for i in range(1, 4):
                if s+i-1>= n:
                    break
                presum += stones[s+i-1]
                ans = max(ans, presum - dp(s+i))
            memo[s] = ans
            return ans
        score = dp(0)
        return 'Alice' if score > 0 else 'Bob' if score < 0 else 'Tie'
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
    
    def stoneGameIII5(self, stoneValue):
        # memorized dp
        n = len(stoneValue)
        
        memo = dict()
        
        def dp(s):
            if s>=n:return 0
            if s in memo:
                return memo[s]
            
            ans = -2**31
            for i in range(1, 4):
                if s+i > n:
                    break
                ans = max(ans, sum(stoneValue[s:s+i]) - dp(s+i))
            memo[s] = ans
            return ans
        
        score = dp(0)
        return 'Alice' if score > 0 else 'Bob' if score < 0 else 'Tie'
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
    
    def stoneGameIII1(self, stoneValue):
        # memorized dp
        n = len(stoneValue)
        memo = dict()
        def dp(s):
            # start index of stonevlaue
            if s >= n:
                return 0
            if s in memo:
                return memo[s]
            
            ans = -2**31
            
            for i in range(1, 4):
                # first 1 to 3
                if s+i>n:
                    break;
                ans = max(ans, sum(stoneValue[s:s+i]) - dp(s+i))
            memo[s] = ans
            return ans
        score  = dp(0)
        return 'Alice' if score > 0 else 'Bob' if score < 0 else 'Tie'
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        

class Solution1:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        # take 1, 2, or 3 stones from the first remaining stones of the row
        # memorized dp, with mimmax process
        
        # state = dp[s], start from index s
        
        # take one, stoneValue[s] - dp[s+1]
        # take two, stoneValue[s,s+1] - dp[s+2]
        # take three, stoneValue[s, s+1, s+2] - dp[s+3]
        # max value of these three branches
        
        # dp[s] > 0
        
        memo = {}
        n = len(stoneValue)
        
        def dp(s):
            if s>=n: return 0
            if s in memo:
                return memo[s]
            
            ans = -2**31  # 这个有错误！，ans=0了，是不对的！
            for i in range(1, 4):
                if s + i > n: # was bad, s+i>=n was not correct! 这个也有错误！写成了s+i>n，也是错误的！
                    break
                ans = max(ans, sum(stoneValue[s:s+i]) - dp(s+i))
            memo[s] = ans
            return ans
        
        score = dp(0)# - sum(stoneValue)/2 跟这个sum(stoneValue)/2没有关系！错误3！
        #print(score, sum(stoneValue)/2)
        return 'Alice' if score > 0 else 'Bob' if score < 0 else 'Tie'
        
    def stoneGameIII2(self, stoneValue: List[int]) -> str:       
        # 采用和类似于stoneGameII的方法，可以吗？-> works!! great 太好了，get一个minmax的求解的模板！！！
        # 残局
        # solve(s) score diff
        # M=1,2,3
        # x=[1,2,3]
        # solve(s) = max(sum(sv[s:s+x-1]) - solve(s+x))
        
        n = len(stoneValue)
        
        cache = dict() # s:score
        
        def solve(s):
            if s>=n: return 0
            if s in cache: return cache[s]
            
            best = -2**31
            presum = 0
            
            for x in range(1, 4):
                if s+x-1 >= n:
                    break
                presum += stoneValue[s+x-1]
                best = max(best, presum - solve(s+x))
            cache[s] = best
            return best
        score = solve(0)
        return 'Alice' if score > 0 else 'Bob' if score < 0 else 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        length = len(stoneValue)
        
        memo = {}
        
        def helper(current_idx):
            if current_idx >= length:
                return 0
            
            if current_idx in memo:
                return memo[current_idx]
            
            res = float('-inf')
            sum = 0
            
            for i in range(3):
                if current_idx + i < length:
                    sum += stoneValue[current_idx + i]
                    res = max(res, sum - helper(current_idx + i + 1))
            
            memo[current_idx] = res
            return res
        
        result = helper(0)
        
        if result == 0:
            return 'Tie'
        elif result > 0:
            return 'Alice'
        return 'Bob'


class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        first, second = self.memo_search(0, stoneValue, {})
        if first > second:
            return 'Alice'
        if first == second:
            return 'Tie'
        return 'Bob'
    
    def memo_search(self, pos, stoneValue, memo):
        if pos in memo:
            return memo[pos]
        
        if pos == len(stoneValue):
            return 0, 0
        
        ans = -sys.maxsize
        value = 0
        for i in range(3):
            if pos + i < len(stoneValue):
                value += stoneValue[pos + i]
                second, first = self.memo_search(pos + i + 1, stoneValue, memo)
                total = first + second + value
                if first + value > ans:
                    ans = first + value
        memo[pos] = ans, total - ans
        return ans, total - ans


class Solution:
    def stoneGameIII(self, stoneValue):
      def dfs(start):
        if start >= len(stoneValue):
          return 0
        
        if dp[start] != None:
          return dp[start]

        i = start
        curSum = 0
        maxValue = -float('inf')

        while i < len(stoneValue) and i < start + 3:
          curSum += stoneValue[i]
          maxValue = max(maxValue, curSum - dfs(i + 1))
          i += 1

        dp[start] = maxValue

        return dp[start]  

      dp = [None] * len(stoneValue)

      res = dfs(0)

    
      if res > 0:
        return 'Alice'
      elif res < 0:
        return 'Bob'
      return 'Tie'  


class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        cursum = 0
        dp1 = [float('-inf')] * (n + 1)
        dp1[-1] = 0
        for i in range(n - 1, -1, -1):
            cursum += stoneValue[i]
            for k in range(3):
                if i + k >= n:
                    break
                dp1[i] = max(dp1[i], cursum - dp1[i + k + 1])
        if dp1[0] > cursum - dp1[0]:
            return 'Alice'
        if dp1[0] < cursum - dp1[0]:
            return 'Bob'
        return 'Tie'
                


class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        # dont take the below, because it can be negative, [-1,-2,-3]
        #if len(stoneValue) <= 3:
        #    return 'Alice'
        p1, p2, p3 = 0, 0, 0
        post_sum = 0
        for i in range(len(stoneValue) - 1, -1, -1):
            val = stoneValue[i]
            post_sum += val
            best = post_sum - min([p1, p2, p3])
            p1, p2, p3 = best, p1, p2
        if p1 > post_sum - p1:
            return 'Alice'
        elif p1 < post_sum - p1:
            return 'Bob'
        else:
            return 'Tie'
        
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        total = [0] * (len(stoneValue) + 4)
        for i in range(len(stoneValue) - 1, -1, -1):
            total[i] = total[(i + 1)] + stoneValue[i]
        dp = [0] * (len(total))
        for i in range(len(stoneValue) - 1, -1, -1):
            dp[i] = total[i] - min(dp[i + 1: i + 4], default = 0)
        
        alice = dp[0]
        bob = total[0] - alice
        if alice > bob:
            return 'Alice'
        elif alice < bob:
            return 'Bob'
        else:
            return 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        # take 1, 2, or 3 stones from the first remaining stones of the row
        
        # memorized dp, with mimmax process
        
        # state = dp[s], start from index s
        
        # take one, stoneValue[s] - dp[s+1]
        # take two, stoneValue[s,s+1] - dp[s+2]
        # take three, stoneValue[s, s+1, s+2] - dp[s+3]
        # max value of these three branches
        
        # dp[s] > 0
        
        memo = {}
        n = len(stoneValue)
        
        def dp(s):
            if s>=n: return 0
            if s in memo:
                return memo[s]
            
            ans = -2**31  # 这个有错误！，ans=0了，是不对的！
            for i in range(1, 4):
                if s + i > n: # was bad, s+i>=n was not correct! 这个也有错误！写成了s+i>n，也是错误的！
                    break
                ans = max(ans, sum(stoneValue[s:s+i]) - dp(s+i))
            memo[s] = ans
            return ans
        
        score = dp(0)# - sum(stoneValue)/2 跟这个sum(stoneValue)/2没有关系！错误3！
        #print(score, sum(stoneValue)/2)
        return 'Alice' if score > 0 else 'Bob' if score < 0 else 'Tie'
        
    def stoneGameIII2(self, stoneValue: List[int]) -> str:       
        # 采用和类似于stoneGameII的方法，可以吗？-> works!! great 太好了，get一个minmax的求解的模板！！！
        # 残局
        # solve(s) score diff
        # M=1,2,3
        # x=[1,2,3]
        # solve(s) = max(sum(sv[s:s+x-1]) - solve(s+x))
        
        n = len(stoneValue)
        
        cache = dict() # s:score
        
        def solve(s):
            if s>=n: return 0
            if s in cache: return cache[s]
            
            best = -2**31
            presum = 0
            
            for x in range(1, 4):
                if s+x-1 >= n:
                    break
                presum += stoneValue[s+x-1]
                best = max(best, presum - solve(s+x))
            cache[s] = best
            return best
        score = solve(0)
        return 'Alice' if score > 0 else 'Bob' if score < 0 else 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:

        length = len(stoneValue)

        # dp[i] denote sum of items selected by Alice subtract sum of Bob from i to last
        dp = {}
        kA = 'Alice'
        kB = 'Bob'
        for index in range(length-1, -1, -1):
            minus = length - index
            rA = rB = 0
            if minus >= 3:  # normal case >=3; three choices
                # choice 1: select all the three
                c1 = stoneValue[index] + stoneValue[index + 1] + stoneValue[index + 2]

                # choice 2: select first two
                c2 = stoneValue[index] + stoneValue[index + 1]

                # choice 3: select first one
                c3 = stoneValue[index]

                # Alice
                rA = max(c1 + dp.get((index + 3, kB), 0), c2 + dp.get((index + 2, kB), 0),
                         c3 + dp.get((index + 1, kB), 0))

                # Bob
                rB = min(-c1 + dp.get((index + 3, kA), 0), -c2 + dp.get((index + 2, kA), 0),
                         -c3 + dp.get((index + 1, kA), 0))
            elif minus == 2:  # remain two, two choices
                # choice 1: select all the two
                c1 = stoneValue[index] + stoneValue[index + 1]

                # choice 2: select the first of the two
                c2 = stoneValue[index]

                # Alice select
                rA = max(c1, c2 + dp.get((index + 1, kB), 0))

                # Bob select
                rB = min(-c1, -c2 + dp.get((index + 1, kA), 0))
            elif minus == 1:  # remain one, only one choice
                c1 = stoneValue[index]
                rA = c1
                rB = -c1

            dp[(index, kA)] = rA
            dp[(index, kB)] = rB

        #print(stoneValue)
        #print(dp)
        result = dp.get((0, kA))
        if result > 0:
            return 'Alice'
        elif result < 0:
            return 'Bob'
        else:
            return 'Tie'

from functools import lru_cache

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        minimal = -2 ** 31
        n = len(stoneValue)
        dp = [minimal] * (n + 1)  # net difference between two players for stones[i:]
        dp[n] = 0  # iterate backwards

        for i in range(n - 1, -1, -1):
            curr_net = 0
            for j in range(1, min(4, n - i + 1)):
                curr_net += stoneValue[i + j - 1]
                dp[i] = max(dp[i], curr_net - dp[i + j])

        return 'Alice' if dp[0] > 0 else 'Bob' if dp[0] < 0 else 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        self.cache = [0] * 50001
        total = sum(stoneValue)
        first = (total + self.helper(stoneValue, 0)) // 2
        second = total - first
        if first > second:
            return 'Alice'
        elif first < second:
            return 'Bob'
        else:
            return 'Tie'
    
    def helper(self, stoneValue, index):
        if self.cache[index]:
            return self.cache[index]
        
        n = len(stoneValue)
        if index == n:
            return 0
        
        cur = 0
        best = -sys.maxsize
        for i in range(3):
            if index + i >= n:
                break
            
            cur += stoneValue[index + i]
            best = max(best, cur - self.helper(stoneValue, index + i + 1))
        
        self.cache[index] = best
        return best


class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        dp = [-float('inf')] * (len(stoneValue) + 5)
        dp[len(stoneValue):len(stoneValue)+5] = [0] * 5
        # postfix= [0] * (len(stoneValue) + 1)
        # for i in range(len(stoneValue)-1, -1, -1):
        #     postfix[i] = postfix[i+1] + stoneValue[i]
        s = stoneValue
        # dp[i], from ith, the value that we can get 
        # because i=0 is Alice's option so we just need to judge how many value we can get at this point 
        
        # for ind in range(len(s)-1, -1, -1):
        #     take = 0
        #     for i in range(3):
        #         if ind + i >= len(s):
        #             break
        #         take += s[ind+i]
        #         dp[ind] = max(dp[ind], take-dp[ind+i+1])
        # if dp[0] == 0:
        #     return 'Tie'
        # return 'Alice' if dp[0] > 0 else 'Bob'
        dp = dict()
        def search(i):
            if i >= len(stoneValue):
                return 0 
            res = -float('inf')
            score = 0
            if i in dp: return dp[i]
            for j in range(3):
                if i + j < len(stoneValue):
                    score += stoneValue[i+j] 
                    res = max(score - search(i+j+1), res)
            dp[i] = res
            return dp[i]
        
        ans = search(0)
        if dp[0] == 0:
            return 'Tie'
        return 'Alice' if dp[0] > 0 else 'Bob'


class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        # take 1, 2, or 3 stones from the first remaining stones of the row
        
        # memorized dp, with mimmax process
        
        # state = dp[s], start from index s
        
        # take one, stoneValue[s] - dp[s+1]
        # take two, stoneValue[s,s+1] - dp[s+2]
        # take three, stoneValue[s, s+1, s+2] - dp[s+3]
        # max value of these three branches
        
        # dp[s] > 0
        
        memo = {}
        n = len(stoneValue)
        
        def dp(s):
            if s>=n: return 0
            if s in memo:
                return memo[s]
            
            ans = -2**31  # 这个有错误！，ans=0了，是不对的！
            for i in range(1, 4):
                if s + i > n: # was bad, s+i>=n was not correct! 这个也有错误！写成了s+i>n，也是错误的！
                    break
                ans = max(ans, sum(stoneValue[s:s+i]) - dp(s+i))
            memo[s] = ans
            return ans
        
        score = dp(0)# - sum(stoneValue)/2
        #print(score, sum(stoneValue)/2)
        return 'Alice' if score > 0 else 'Bob' if score < 0 else 'Tie'
        
    def stoneGameIII2(self, stoneValue: List[int]) -> str:       
        # 采用和类似于stoneGameII的方法，可以吗？-> works!! great 太好了，get一个minmax的求解的模板！！！
        # 残局
        # solve(s) score diff
        # M=1,2,3
        # x=[1,2,3]
        # solve(s) = max(sum(sv[s:s+x-1]) - solve(s+x))
        
        n = len(stoneValue)
        
        cache = dict() # s:score
        
        def solve(s):
            if s>=n: return 0
            if s in cache: return cache[s]
            
            best = -2**31
            presum = 0
            
            for x in range(1, 4):
                if s+x-1 >= n:
                    break
                presum += stoneValue[s+x-1]
                best = max(best, presum - solve(s+x))
            cache[s] = best
            return best
        score = solve(0)
        return 'Alice' if score > 0 else 'Bob' if score < 0 else 'Tie'

from functools import lru_cache

class Solution:
  @lru_cache(None)
  def recursive(self, i):
    if i >= self.n:
      return 0
    ans, score = float('-inf'), 0
    for k in range(3):
      if i + k < self.n:
        score += self.s[i + k]
        ans = max(ans, score - self.recursive(i + k + 1))
    return ans
  def stoneGameIII(self, stoneValue: List[int]) -> str:
    self.n, self.s = len(stoneValue), stoneValue
    self.recursive.cache_clear()
    x = self.recursive(0)
    return 'Alice' if x > 0 else 'Tie' if x == 0 else 'Bob'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        dp = [[-math.inf, -math.inf] for _ in range(n + 1)]
        dp[-1] = [0, 0]
        for i in range(n - 1, -1, -1):
            for j in range(i + 1, min(i + 4, n + 1)):
                if dp[i][0] < dp[j][1] + sum(stoneValue[i:j]):
                    dp[i][0] = dp[j][1] + sum(stoneValue[i:j])
                    dp[i][1] = dp[j][0]
        alice, bob = dp[i]
        # print(dp)
        if alice > bob:
            return 'Alice'
        elif alice < bob:
            return 'Bob'
        else:
            return 'Tie'

class Solution:
    def stoneGameIII(self, stones: List[int]) -> str:
        rowlen=len(stones)
        dp=[0] * (rowlen+1)
        i=rowlen-1
        
        
        while i >= 0:
            
            answer=-float('inf')
            
            answer=max(answer,stones[i] - dp[i+1])
            
            if i+1 < rowlen:
                answer=max(answer,stones[i]+stones[i+1] - dp[i+2])  
                
            if i+2 < rowlen:
                answer=max(answer,stones[i]+stones[i+1]+stones[i+2] - dp[i+3])
        
            dp[i] = answer 
            i-=1
        
        print(dp)
        if dp[0] > 0:
            return 'Alice'
        elif dp[0] < 0:
            return 'Bob'
        else:
            return 'Tie'
        
        
        
        
        '''
        # Recursion + TopDown
        rowlen=len(stones)
        index=0
        memo=[-1] * rowlen
             
        def helper(index,memo):
            
            if index >= rowlen:
                return 0
            elif memo[index] != -1:
                return memo[index] 
            else:
                answer=-float('inf')
                answer=max(answer,stones[index] - helper(index+1,memo))
                if index + 1 < rowlen:
                    answer=max(answer,stones[index]+stones[index+1] - helper(index+2,memo))
                
                if index + 2 < rowlen:
                    answer=max(answer,stones[index]+stones[index+1]+stones[index+2] - helper(index+3,memo))
                
                memo[index]=answer
                return memo[index]      
                
        answer=helper(0,memo)
        print(answer)
        
        if answer < 0:
            return 'Bob'
        elif answer > 0:
            return 'Alice'
        else:
            return 'Tie'
            
        '''      

class Solution:
    def stoneGameIII(self, stoneValue):
        # memorized dp
        n = len(stoneValue)
        memo = dict()
        def dp(s):
            # start index of stonevlaue
            if s >= n:
                return 0
            if s in memo:
                return memo[s]
            
            ans = -2**31
            
            for i in range(1, 4):
                # first 1 to 3
                if s+i>n:
                    break;
                ans = max(ans, sum(stoneValue[s:s+i]) - dp(s+i))
            memo[s] = ans
            return ans
        score  = dp(0)
        return 'Alice' if score > 0 else 'Bob' if score < 0 else 'Tie'
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        

class Solution1:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        # take 1, 2, or 3 stones from the first remaining stones of the row
        # memorized dp, with mimmax process
        
        # state = dp[s], start from index s
        
        # take one, stoneValue[s] - dp[s+1]
        # take two, stoneValue[s,s+1] - dp[s+2]
        # take three, stoneValue[s, s+1, s+2] - dp[s+3]
        # max value of these three branches
        
        # dp[s] > 0
        
        memo = {}
        n = len(stoneValue)
        
        def dp(s):
            if s>=n: return 0
            if s in memo:
                return memo[s]
            
            ans = -2**31  # 这个有错误！，ans=0了，是不对的！
            for i in range(1, 4):
                if s + i > n: # was bad, s+i>=n was not correct! 这个也有错误！写成了s+i>n，也是错误的！
                    break
                ans = max(ans, sum(stoneValue[s:s+i]) - dp(s+i))
            memo[s] = ans
            return ans
        
        score = dp(0)# - sum(stoneValue)/2 跟这个sum(stoneValue)/2没有关系！错误3！
        #print(score, sum(stoneValue)/2)
        return 'Alice' if score > 0 else 'Bob' if score < 0 else 'Tie'
        
    def stoneGameIII2(self, stoneValue: List[int]) -> str:       
        # 采用和类似于stoneGameII的方法，可以吗？-> works!! great 太好了，get一个minmax的求解的模板！！！
        # 残局
        # solve(s) score diff
        # M=1,2,3
        # x=[1,2,3]
        # solve(s) = max(sum(sv[s:s+x-1]) - solve(s+x))
        
        n = len(stoneValue)
        
        cache = dict() # s:score
        
        def solve(s):
            if s>=n: return 0
            if s in cache: return cache[s]
            
            best = -2**31
            presum = 0
            
            for x in range(1, 4):
                if s+x-1 >= n:
                    break
                presum += stoneValue[s+x-1]
                best = max(best, presum - solve(s+x))
            cache[s] = best
            return best
        score = solve(0)
        return 'Alice' if score > 0 else 'Bob' if score < 0 else 'Tie'

from functools import lru_cache
class Solution(object):
    def stoneGameIII(self, Values):
        N = len(Values)
        @lru_cache(None)
        def dp(i):
            if i>=N:
                return (0,0)
            if i == N-1:
                return (Values[-1], 0)
            one, two, three = -float('inf'), -float('inf'), -float('inf')
            one = (Values[i]+dp(i+1)[1], dp(i+1)[0])
            if i< N-1:
                two =(Values[i]+Values[i+1]+dp(i+2)[1], dp(i+2)[0])
                one = max(one, two)
            if i<N-2:
                three = (Values[i]+Values[i+1]+Values[i+2]+dp(i+3)[1], dp(i+3)[0])
                one = max(one, three)
            return one
        res = dp(0)
        return 'Alice' if res[0]>res[1] else 'Bob' if res[1]>res[0] else 'Tie'



class Solution:
    def stoneGameIII(self, sv: List[int]) -> str:
        n=len(sv)
        sv.append(0)
        sv.append(0)
        dp=[0 for _ in range(n+3)]
        for i in range(n-1,-1,-1):
            dp[i]=max(sv[i]-dp[i+1],sv[i]+sv[i+1]-dp[i+2], sv[i]+sv[i+1]+sv[i+2]-dp[i+3])
        # print(dp)
        if dp[0]>0:
            return 'Alice'
        elif dp[0]<0:
            return 'Bob'
        return 'Tie'

                
                


class Solution:
    def stoneGameIII(self, stones: List[int]) -> str:
        #dp[i]: max value can get after i piles stone removed
        n = len(stones)
        dp = [-math.inf for _ in range(n + 1)]
        dp[n] = 0
        prefix = [0 for _ in range(n + 1)]
        for i in range(1, n + 1):
            prefix[i] = prefix[i - 1] + stones[i - 1]
        
        for i in range(n - 1, -1, -1):
            for k in range(1, 4):
                if i + k > n:
                    break
                dp[i] = max(dp[i], sum(stones[i: i + k]) + prefix[-1] - prefix[i + k] - dp[i + k])
                
        if dp[0] * 2 > sum(stones):
            return 'Alice'
        elif dp[0] * 2 < sum(stones):
            return 'Bob'
        else:
            return 'Tie'
        
        


class Solution:
    
    def stoneGameIII(self, stoneValue):
        # memorized dp
        n = len(stoneValue)
        
        memo = dict()
        
        def dp(s):
            if s>=n:return 0
            if s in memo:
                return memo[s]
            
            ans = -2**31
            for i in range(1, 4):
                if s+i > n:
                    break
                ans = max(ans, sum(stoneValue[s:s+i]) - dp(s+i))
            memo[s] = ans
            return ans
        
        score = dp(0)
        return 'Alice' if score > 0 else 'Bob' if score < 0 else 'Tie'
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
    
    def stoneGameIII1(self, stoneValue):
        # memorized dp
        n = len(stoneValue)
        memo = dict()
        def dp(s):
            # start index of stonevlaue
            if s >= n:
                return 0
            if s in memo:
                return memo[s]
            
            ans = -2**31
            
            for i in range(1, 4):
                # first 1 to 3
                if s+i>n:
                    break;
                ans = max(ans, sum(stoneValue[s:s+i]) - dp(s+i))
            memo[s] = ans
            return ans
        score  = dp(0)
        return 'Alice' if score > 0 else 'Bob' if score < 0 else 'Tie'
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        

class Solution1:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        # take 1, 2, or 3 stones from the first remaining stones of the row
        # memorized dp, with mimmax process
        
        # state = dp[s], start from index s
        
        # take one, stoneValue[s] - dp[s+1]
        # take two, stoneValue[s,s+1] - dp[s+2]
        # take three, stoneValue[s, s+1, s+2] - dp[s+3]
        # max value of these three branches
        
        # dp[s] > 0
        
        memo = {}
        n = len(stoneValue)
        
        def dp(s):
            if s>=n: return 0
            if s in memo:
                return memo[s]
            
            ans = -2**31  # 这个有错误！，ans=0了，是不对的！
            for i in range(1, 4):
                if s + i > n: # was bad, s+i>=n was not correct! 这个也有错误！写成了s+i>n，也是错误的！
                    break
                ans = max(ans, sum(stoneValue[s:s+i]) - dp(s+i))
            memo[s] = ans
            return ans
        
        score = dp(0)# - sum(stoneValue)/2 跟这个sum(stoneValue)/2没有关系！错误3！
        #print(score, sum(stoneValue)/2)
        return 'Alice' if score > 0 else 'Bob' if score < 0 else 'Tie'
        
    def stoneGameIII2(self, stoneValue: List[int]) -> str:       
        # 采用和类似于stoneGameII的方法，可以吗？-> works!! great 太好了，get一个minmax的求解的模板！！！
        # 残局
        # solve(s) score diff
        # M=1,2,3
        # x=[1,2,3]
        # solve(s) = max(sum(sv[s:s+x-1]) - solve(s+x))
        
        n = len(stoneValue)
        
        cache = dict() # s:score
        
        def solve(s):
            if s>=n: return 0
            if s in cache: return cache[s]
            
            best = -2**31
            presum = 0
            
            for x in range(1, 4):
                if s+x-1 >= n:
                    break
                presum += stoneValue[s+x-1]
                best = max(best, presum - solve(s+x))
            cache[s] = best
            return best
        score = solve(0)
        return 'Alice' if score > 0 else 'Bob' if score < 0 else 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        dp = [float('-inf')] * n
        
        def dfs(i):
            if i >= n: return 0
            if dp[i] != float('-inf'): return dp[i]
            
            ssum = 0
            for j in range(3):
                if i + j < n:
                    ssum += stoneValue[i+j]
                    dp[i] = max(dp[i], ssum - dfs(i+j+1))
            return dp[i]
        score = dfs(0)
        if score > 0: return 'Alice'
        elif score < 0: return 'Bob'
        return 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        memo = {}
        
        def dfs(start):
            if start >= len(stoneValue):
                return 0
            
            if start in memo:
                return memo[start]
            
            memo[start] = float('-inf') 
            score = 0
            
            for i in range(start, min(len(stoneValue), start + 3)):
                score += stoneValue[i]
                memo[start] = max(memo[start], score - dfs(i + 1))
            
            return memo[start]
        
        score = dfs(0)  
        return 'Tie' if score == 0 else 'Alice' if score > 0 else 'Bob'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        @lru_cache(None)
        def dp(cur):
            if cur >= n:
                return 0, 0
            first, second = -math.inf, -math.inf
            for i in range(1, 4):
                first_tmp, second_tmp = dp(cur + i)
                if first < second_tmp + sum(stoneValue[cur:cur + i]):
                    first = second_tmp + sum(stoneValue[cur:cur + i])
                    second = first_tmp
            return first, second
        alice, bob = dp(0)
        if alice > bob:
            return 'Alice'
        elif alice < bob:
            return 'Bob'
        else:
            return 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        self.cache = {}
        score = self.solve(0, stoneValue)
        return 'Alice' if score > 0 else 'Bob' if score < 0 else 'Tie'
    

    def solve(self, i, stoneValue): # score diff
        n = len(stoneValue)
        if i>=n: 
            return 0

        if i in self.cache: 
            return self.cache[i]

        res = float('-inf')
        presum = 0

        for x in range(1, 4):
            if i+x-1>=n:
                break
            presum += stoneValue[i+x-1]
            res = max(res, presum - self.solve(i+x, stoneValue)) # min-max process
        self.cache[i] = res
        return res
    
    
    
    


class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        dp = [-float('inf')] * (len(stoneValue) + 5)
        dp[len(stoneValue):len(stoneValue)+5] = [0] * 5
        postfix= [0] * (len(stoneValue) + 1)
        for i in range(len(stoneValue)-1, -1, -1):
            postfix[i] = postfix[i+1] + stoneValue[i]
        s = stoneValue
        # dp[i], from ith, the value that we can get 
        # because i=0 is Alice's option so we just need to judge how many value we can get at this point 
        
        # for ind in range(len(s)-1, -1, -1):
        #     take = 0
        #     for i in range(3):
        #         if ind + i >= len(s):
        #             break
        #         take += s[ind+i]
        #         dp[ind] = max(dp[ind], take-dp[ind+i+1])
        # if dp[0] == 0:
        #     return 'Tie'
        # return 'Alice' if dp[0] > 0 else 'Bob'
        dp = dict()
        def search(i):
            if i >= len(stoneValue):
                return 0 
            res = -float('inf')
            score = 0
            if i in dp: return dp[i]
            for j in range(3):
                if i + j < len(stoneValue):
                    score += stoneValue[i+j] 
                    res = max(score - search(i+j+1), res)
            dp[i] = res
            return dp[i]
        
        ans = search(0)
        if dp[0] == 0:
            return 'Tie'
        return 'Alice' if dp[0] > 0 else 'Bob'
        # class Solution:
#     def stoneGameIII(self, stoneValue: List[int]) -> str:
#         memo = {}
        
#         def dfs(start):
#             if start >= len(stoneValue):
#                 return 0
            
#             if start in memo:
#                 return memo[start]
            
#             memo[start] = float('-inf') 
#             score = 0
            
#             for i in range(start, min(len(stoneValue), start + 3)):
#                 score += stoneValue[i]
#                 memo[start] = max(memo[start], score - dfs(i + 1))
            
#             return memo[start]
        
#         score = dfs(0)  
#         return 'Tie' if score == 0 else 'Alice' if score > 0 else 'Bob'


class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        
        self.memo = collections.defaultdict(int)
        self.stoneValue = stoneValue
        score = self.dfs(0)  
        return 'Tie' if score == 0 else 'Alice' if score > 0 else 'Bob'
        
    def dfs(self,start):
        if start >= len(self.stoneValue):
            return 0

        if start in self.memo:
            return self.memo[start]
        
        res = float('-inf')
        score = 0

        for i in range(start, min(len(self.stoneValue), start + 3)):
            score += self.stoneValue[i]
            res = max(res, score - self.dfs(i + 1))
        
        self.memo[start] = res
        
        return res
        


class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        memo = {}
        post_sum = [0] * (n + 1)
        for i in range(n)[::-1]:
            post_sum[i] = stoneValue[i] + post_sum[i + 1]
        
        def dfs(i):
            if i >= n:
                return 0
            
            if i in memo:
                return memo[i]
            
            res = float('-inf')
            cur = 0
            for j in range(i, min(i + 3, n)):
                cur += stoneValue[j]
                res = max(res, cur + post_sum[j + 1] - dfs(j + 1))
            
            memo[i] = res
            return res
        
        res = dfs(0)
        if res * 2 == post_sum[0]:
            return 'Tie'
        
        if res * 2 > post_sum[0]:
            return 'Alice'
        
        return 'Bob'


fmax = lambda x,y: x if x>y else y
class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        
        i = n - 1
        
        i1, i2, i3 = 0, 0, 0
        
        while i>=0:
            ans = float('-inf')
            
            ans = fmax(ans, stoneValue[i] - i1)
            
            if i+1 < n:
                ans = fmax(ans, stoneValue[i] + stoneValue[i+1] - i2)
                
            if i+2 < n:
                ans = fmax(ans, stoneValue[i] + stoneValue[i+1] + stoneValue[i+2] - i3)
                
            i3 = i2
            i2 = i1
            i1 = ans
            i -= 1
        
        if i1 > 0:
            return 'Alice'
        elif i1 < 0:
            return 'Bob'
        return 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        best = {}; S =0; N = len(stoneValue)
        cumsum = [0 for val in stoneValue]+[0];
        for ii in range(len(stoneValue)-1,-1,-1):
            S = S+stoneValue[ii]
            cumsum[ii] = S
        def findbest(index,stoneValue):
#            print(index,best)
            if index in best:
                res = best[index]
            elif index==len(stoneValue)-1:
                res= stoneValue[-1]
            elif index>=len(stoneValue):
                res = 0  
            else:
                res = -10000000
                for j in range(index+1,min(index+4,N+1)):
                    res = max(res,sum(stoneValue[index:j]) + cumsum[j]-findbest(j,stoneValue))
#                    print(index,j,res)
            best[index] = res
            return best[index]
        res= findbest(0,stoneValue)
#        print(best)
        if res>sum(stoneValue)/2:
            return 'Alice'
        elif res<sum(stoneValue)/2:
            return 'Bob'
        else:
            return 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        @lru_cache(None)
        def helper(idx):
            if idx == len(stoneValue): return 0, idx
            # if idx + 2 >= len(stoneValue) - 1: return sum(stoneValue[idx:]), len(stoneValue)
            score, max_score = 0, -sys.maxsize + 1
            op_idx = idx + 1
            for num in range(3):
                if idx + num < len(stoneValue):
                    score += stoneValue[idx + num]
                    b_score, a_idx = helper(idx + num + 1)
                    if helper(a_idx)[0] + score >= max_score:
                        max_score = helper(a_idx)[0] + score
                        op_idx = idx + num + 1
            return max_score, op_idx
        
        score, op_idx = helper(0)
        op_score = helper(op_idx)[0]
        
        # print(score, op_idx)
        if score > op_score: return 'Alice'
        elif score == op_score: return 'Tie'
        else: return 'Bob'
            


class Solution:
    def stoneGameIII(self, stoneValue: list) -> str:
        def play(preSum, index, cache):
            if index == len(preSum) - 1:
                return preSum[index]
            if index in cache:
                return cache[index]
            res = -2**31
            for i in range(1, 4):
                if index + i >= len(preSum):
                    break
                take = preSum[index] - preSum[index + i]
                res = max(
                    res,
                    take + preSum[index + i] - play(preSum, index + i, cache))
            cache[index] = res

            return res

        for i in range(len(stoneValue) - 2, -1, -1):
            stoneValue[i] += stoneValue[i + 1]
        aliceScore = play(stoneValue + [0], 0, {})
        bobScore = stoneValue[0] - aliceScore
        if bobScore > aliceScore:
            return 'Bob'
        elif aliceScore > bobScore:
            return 'Alice'
        else:
            return 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        dp = {}
        piles = stoneValue
        n = len(piles)
        sums = 0
        for pile in piles:
            sums += pile

        def rec_max(i,n,sums):
            if i == n:
                return 0
            if i in dp:
                return dp[i][0]
            m = min(3,n-i)
            res_sum = float('-inf')
            res_gap = float('-inf')
            remains = sums
            for x in range(m):
                remains -= piles[i+x]
                other = rec_max(i+x+1,n,remains)
                res = sums - other
                gap = res - other
                if gap > res_gap:
                    res_gap = gap
                    res_sum = res
            dp[i] = res_sum,res_gap
            return res_sum
        rec_max(0,n,sums) 
        res = dp[0][1]
        if res < 0:
            return 'Bob'
        elif res > 0:
            return 'Alice'
        else:
            return 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        memo = {}
        def helper(i,total):
            if i>=n:
                return 0
            elif (i) in memo:
                return memo[i]
            res = -math.inf
            for x in range(1, min(4, n-i+1)):
                s = sum(stoneValue[i:i+x])
                res = max(res, total - helper(i+x,total-s))
            memo[i] = res
            return res
        
        total = sum(stoneValue)
        a = helper(0,total)
        b = total - a
        if a == b:
            return 'Tie'
        elif a > b:
            return 'Alice'
        else:
            return 'Bob'

#dp
#f(>=N) = 0
#f(i) = suffixsum[i] - min(f(i+x) for x in range(1,4))
class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        N = len(stoneValue)
        dp = [0] * (N+3)
        acc = 0
        for i in range(N-1, -1, -1):
            acc += stoneValue[i]
            dp[i] = acc - min(dp[i+x] for x in range(1,4))
        alice = dp[0]
        bob = acc - alice
        if alice > bob:
            return 'Alice'
        elif alice == bob:
            return 'Tie'
        else:
            return 'Bob'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        for i in range(n-2, -1,-1):
            stoneValue[i] += stoneValue[i+1]
        
        from functools import lru_cache
        @lru_cache(None)
        def dp(i):
            if i >= n:
                return 0
            return stoneValue[i] - min(dp(i+x) for x in [1,2,3])
            
        
        Alice = dp(0)
        Bob = stoneValue[0] - Alice
        
        if Alice > Bob:
            return 'Alice'
        elif Alice < Bob:
            return 'Bob'
        else:
            return 'Tie'
        
    def stoneGameIII(self, A: List[int]) -> str:
        @lru_cache(None)
        def dp(i):
            # beyond the scope, return 0
            if i>=len(A):return 0
            # if only one element left, return this value
            if i==len(A)-1:return A[-1]
            # three actions: pick up 1, pick up 2, pick up 3. 
            # alice_score_of_alice at i = 
            #  max(action_score_of_alice - (action_score_of_bob at i+j+1) for action in 3 cases)
            res = -float('inf')
            for j in range(3):
                if i+j<len(A):
                    this_res = sum(A[i:i+j+1])-dp(i+j+1)
                    res = max(res, this_res)
            return res
        
        if dp(0)>0:return 'Alice'
        elif dp(0)<0:return 'Bob'
        else:return 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        
        self.memo = collections.defaultdict(int)
        self.stoneValue = stoneValue
        score = self.dfs(0)  
        return 'Tie' if score == 0 else 'Alice' if score > 0 else 'Bob'
        
    def dfs(self,start):
        if start >= len(self.stoneValue):
            return 0

        if start in self.memo:
            return self.memo[start]
        
        self.memo[start] = float('-inf')
        score = 0

        for i in range(start, min(len(self.stoneValue), start + 3)):
            score += self.stoneValue[i]
            self.memo[start] = max(self.memo[start], score - self.dfs(i + 1))

        return self.memo[start]
        


class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        dp = [0]*len(stoneValue)
        for i in range(len(stoneValue)-1, -1, -1):
            ans = float('-inf')
            ans = max(ans, stoneValue[i] - (dp[i+1] if i+1<len(stoneValue) else 0))
            if i+1 < len(stoneValue):
                ans = max(ans, stoneValue[i] + stoneValue[i+1] - (dp[i+2] if i+2 < len(stoneValue) else 0))
            
            if i+2 < len(stoneValue):
                ans = max(ans, stoneValue[i] + stoneValue[i+1] + stoneValue[i+2] - (dp[i+3] if i+3<len(stoneValue) else 0))
            dp[i]  = ans 
            # num += stoneValue[i] # s[i]
            # ans = max(ans, num-(dp[i+1] if i+1<len(stoneValue) else 0))            
            # # if i+1<len(stoneValue):
            # #     num += stoneValue[i+1] # s[i]+s[i+1]
            # #     ans = max(ans, num-(dp[i+2] if i+2<len(stoneValue) else 0))
            # #     dp[i] = ans
            # # if i+2<len(stoneValue):
            # #     num += stoneValue[i+2] # s[i]+s[i+1]+s[i+2]
            # #     ans = max(ans, num-(dp[i+3] if i+3<len(stoneValue) else 0))
            # #     dp[i] = ans
            # dp[i] = ans

        if dp[0]>0: return 'Alice'
        elif dp[0]<0: return 'Bob'
        else: return 'Tie'
# dp[i] means the difference between the scores of Alice and Bob (relative score the current player can obtain). We want to maximize this difference, in order to make Alice win. Therefore, we traverse the list from the end to the beginning, and calculate this difference as max(s[i]-dp[i+1], s[i]+s[i+1]-dp[i+2], s[i]+s[i+1]+s[i+2]-dp[i+3]). Of course, if any index runs over the boundary of the list, no need to calculate it.



#dp
#f(i) = suffixsum[i] - min(f(i+x) for x in range(1,4))
class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        memo = dict()
        def dfs(i):
            if i >= N:
                return 0
            if i in memo:
                return memo[i]
            memo[i] = suffixsum[i] - min([dfs(i+x) for x in range(1, 4)])
            return memo[i]
        N = len(stoneValue)
        suffixsum, acc = [0] * N, 0
        for i, v in enumerate(reversed(stoneValue)):
            acc += v
            suffixsum[~i] = acc
        alice = dfs(0)
        bob = suffixsum[0] - alice
        if alice > bob:
            return 'Alice'
        elif alice == bob:
            return 'Tie'
        else:
            return 'Bob'

class Solution:    
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        l = len(stoneValue)
        dp = [0]*(l+1)
        for i in range(l-1,-1,-1):
            val = stoneValue[i]
            dp[i] = val - dp[i+1]
            if i+1 < l:
                val += stoneValue[i+1]
                dp[i] = max(dp[i], val - dp[i+2])
            if i+2 < l:
                val += stoneValue[i+2]
                dp[i] = max(dp[i], val - dp[i+3])
        if dp[0] > 0:
            return 'Alice'
        elif dp[0] == 0:
            return 'Tie'
        else:
            return 'Bob'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        memo = {}
        def dfs(stoneValue, i, memo):
            if i in memo:
                return memo[i]
            if i >= len(stoneValue):
                return 0
            if i == len(stoneValue) - 1:
                return stoneValue[i]
            
            maxi = stoneValue[i] + min(dfs(stoneValue, i+2, memo), dfs(stoneValue, i+3, memo), dfs(stoneValue, i+4, memo))
            # print(maxi)
            if i+1 <len(stoneValue):
                maxi = max(maxi, stoneValue[i] + stoneValue[i+1] + min(dfs(stoneValue, i+3, memo), dfs(stoneValue, i+4, memo), dfs(stoneValue, i+5, memo)))
            # print(maxi)
            if i+2 < len(stoneValue):
                maxi = max(maxi, sum(stoneValue[i:i+3]) + min(dfs(stoneValue, i+4, memo), dfs(stoneValue, i+5, memo), dfs(stoneValue, i+6, memo)))
            # print(maxi)
            # print(stoneValue, maxi)
            memo[i] = maxi
            return maxi
            
            
            
        aliceScore = dfs(stoneValue, 0, memo)
        # print(aliceScore)
        bobScore = sum(stoneValue) - aliceScore
        # print(bobScore)
        
        
        if aliceScore > bobScore:
            return 'Alice'
        
        elif aliceScore < bobScore:
            return 'Bob'
        
        return 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        record = {}
        def helper(i):
            if i in record:
                return record[i]
            if i >= len(stoneValue):
                return [0,0]
            a, b = float('-inf'), float('-inf')
            for x in range(i, min(i+3, len(stoneValue))):
                temp = helper(x+1)
                tempa, tempb = sum(stoneValue[i:x+1])+temp[1], temp[0]
                if tempa > a:
                    a, b = tempa, tempb
            record[i] = [a, b]
            return [a,b]
        
        a, b = helper(0)
        #print(a,b)
        if a > b:
            return 'Alice'
        elif a < b:
            return 'Bob'
        else:
            return 'Tie'


#dp
#f(i) = suffixsum[i] - min(f(i+x) for x in range(1,4))
class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        memo = dict()
        def dfs(i):
            if i > N-1:
                return 0
            if i in memo:
                return memo[i]
            memo[i] = suffixsum[i] - min([dfs(i+x) for x in range(1, 4)])
            return memo[i]
        N = len(stoneValue)
        suffixsum, acc = [0] * N, 0
        for i, v in enumerate(reversed(stoneValue)):
            acc += v
            suffixsum[~i] = acc
        alice = dfs(0)
        bob = suffixsum[0] - alice
        if alice > bob:
            return 'Alice'
        elif alice == bob:
            return 'Tie'
        else:
            return 'Bob'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        memo = [float('-inf')] * (n + 1)
        score = 0
        @lru_cache
        def dfs(start, score=0):
            for i in range(start, min(n, start + 3)):
                score += stoneValue[i]
                memo[start] = max(memo[start], score - dfs(i + 1))
            return memo[start] if memo[start] != float('-inf') else 0 
        return 'Tie' if dfs(0) == 0 else 'Alice' if dfs(0) > 0 else 'Bob'
        
        


class Solution:
    def stoneGameIII(self, nums: List[int]) -> str:
        presum = list(itertools.accumulate(nums))
        def sum(i, j):
            if i == 0:
                return presum[j]
            return presum[j] - presum[i-1]
        
        n = len(nums)
        if n > 1:
            nums[-2] = max(sum(n-2, n-2), sum(n-2, n-1))
        if n > 2:
            # print(f' {nums[n-3]}+{sum(n-2, n-1)}-{nums[-2]}')
            nums[-3] = max(nums[n-3]+sum(n-2, n-1)-nums[-2], sum(n-3, n-2), sum(n-3, n-1))
        for i in range(n-4, -1, -1):
            get_one = nums[i] + sum(i+1, n-1) - nums[i+1]
            get_two = sum(i, i+1) + sum(i+2, n-1) - nums[i+2]
            get_three = sum(i, i+2) + sum(i+3, n-1) - nums[i+3]
            nums[i] = max([get_one, get_two, get_three])
        # print(nums)
        if nums[0] == sum(0, n-1)/2:
            return 'Tie'
        elif nums[0] > sum(0, n-1)/2:
            return 'Alice'
        return 'Bob'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        total = sum(stoneValue)
        dp = {}
        alice_get = self.find_score(stoneValue, 0, dp)
        if alice_get * 2 > total:
            return 'Alice'
        elif alice_get * 2 < total:
            return 'Bob'
        else:
            return 'Tie'
    
    
    def find_score(self, stoneValue, i, dp):
        if i in dp:
            return dp[i]
        if i == len(stoneValue) - 1:
            return stoneValue[i]
        elif i >= len(stoneValue):
            return 0
        elif i == len(stoneValue) - 2:
            return max(stoneValue[i] + stoneValue[i + 1], stoneValue[i])
        else:
            dp[i] = max(stoneValue[i] + min(self.find_score(stoneValue, i + 2, dp), self.find_score(stoneValue, i + 3, dp),self.find_score(stoneValue, i + 4, dp)),
                        stoneValue[i] + stoneValue[i + 1] + min(self.find_score(stoneValue, i + 5, dp), self.find_score(stoneValue, i + 3, dp),self.find_score(stoneValue, i + 4, dp)),
                        stoneValue[i] + stoneValue[i + 1] + stoneValue[i + 2] + min(self.find_score(stoneValue, i + 5, dp), self.find_score(stoneValue, i + 6, dp),self.find_score(stoneValue, i + 4, dp))        
            )
            return dp[i]

from functools import lru_cache
class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        # time complexity: O(n)
        # space complexity: O(n)
        @lru_cache(maxsize=None)
        def score(i):
            if i >= len(stoneValue): return 0
            return max([sum(stoneValue[i:i+k]) - score(i+k) for k in [1,2,3]])
        
        s = score(0)
        if s > 0: return 'Alice'
        elif s < 0: return 'Bob'
        else: return 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        
        n = len(stoneValue)
        dp = [float('-inf')] * n
        dp[-1] = stoneValue[-1]
        for i in range(n - 2, -1, -1):
            s = 0
            for j in range(i, i + 3):
                s += stoneValue[j] if j < n else 0
                nxt = dp[j + 1] if j + 1 < n else 0
                dp[i] = max(dp[i], s - nxt)
        
                
                
#         @lru_cache(None)
#         def dp(cur):
#             if cur == len(stoneValue) - 1:
#                 return stoneValue[cur]
#             if cur >= len(stoneValue):
#                 return 0
#             ret = float('-inf')
#             s = 0
#             for i in range(3):
#                 nxt = dp(cur + i + 1)
#                 s += stoneValue[cur + i] if cur + i < len(stoneValue) else 0
#                 ret = max(ret, s - nxt)
#             return ret

#         ans = dp(0)
        print(dp)
        ans = dp[0]
        if ans > 0:
            return 'Alice'
        elif ans < 0:
            return 'Bob'
        else:
            return 'Tie'

            


# Relative easy DP problem, time and space complexity are both O(N)
from functools import lru_cache
class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        c=0
        sums=[]
        for i in range(len(stoneValue)-1,-1,-1):
            c+=stoneValue[i]
            sums.append(c)
        @lru_cache(None)
        def optimalValue(s):
            if not s:
                return 0
            return max([sums[s-1]-optimalValue(s-i) for i in range(1,4) if s-i>=0])
        half=0.5*sums[-1]
        res=optimalValue(len(stoneValue))
        return 'Alice' if res>half else 'Bob' if res<half else 'Tie'


class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        
        n = len(stoneValue)
        presum = [0] * (n + 1)
        for i, num in enumerate(stoneValue):
            presum[i+1] = presum[i] + num
        presum += [presum[-1]] * 3
        
        dp = [[0] * 2 for _ in range(n+3)]
        for i in range(n-1, -1, -1):
            for k in range(2):
                dp[i][k] = max(-dp[j][1-k] + presum[j] - presum[i] for j in range(i+1, i+4))
        
        if dp[0][0] > 0:
            return 'Alice'
        elif dp[0][0] < 0:
            return 'Bob'
        else:
            return 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        stone_sum = 0
        dp = [0] * (len(stoneValue) + 1) + [float('inf')] * 2
        for i in range(len(stoneValue) - 1, -1, -1):
            stone_sum += stoneValue[i]
            chose = min(dp[i+1], dp[i+2], dp[i+3])
            dp[i] = stone_sum - chose
        if dp[i] > stone_sum / 2: return 'Alice'
        elif dp[i] < stone_sum / 2: return 'Bob'
        else: return 'Tie'


# Sample [1,2,3,7], max gain at each step: [6, 12, 10, 7, 0]
# for [9,-12,8,12,-12,-16,-13,-11,2,2,-10,-5,13,12,-4,13,4,-4,-16,6,-2,13,-8]
# exp [-7, -12, 0, -4, -16, -4, -20, 12, 23, 21, -7, 27, 32, 19, -5, 24, 11, 7, -18, 17, 11, 13, -8, 0]

class Solution:
    # TLE
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        
        # remaining total value at each index
        remain = list(itertools.accumulate(stoneValue[::-1]))[::-1]
        
        @lru_cache(None)
        def dp(idx):
            if idx >= len(stoneValue):
                return 0
            return remain[idx] - min(dp(idx+i) for i in range(1,4))
        
        first = dp(0)
        second = remain[0] - first
        # print([dp(i) for i in range(len(stoneValue))])
        return 'Alice' if first > second else 'Tie' if first == second else 'Bob'
        

    def stoneGameIII(self, stoneValue: List[int]) -> str:
        
        # remaining total value at each index
        remain = list(itertools.accumulate(stoneValue[::-1]))[::-1]
        n = len(stoneValue)
        dp = [0] * (n + 4)
        
        for idx in range(n-1,-1,-1):
            dp[idx] = remain[idx] - min(dp[idx+i] for i in range(1,4))
        
        first = dp[0]
        second = remain[0] - first
        print([dp[i] for i in range(len(stoneValue))])
        return 'Alice' if first > second else 'Tie' if first == second else 'Bob'




class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        dic = collections.defaultdict(int)
        
        sums = {-1: 0}
        total = sum(stoneValue)
        for i, s in enumerate(stoneValue):
            sums[i] = sums[i - 1] + s
        for i in sums:
            sums[i] = total - sums[i] + stoneValue[i]
        sums.pop(-1)
        
        def dfs(s=0):
            if s not in dic and s < len(stoneValue):
                dic[s] = sums[s] - min([dfs(s + i + 1) for i in range(3)])
            return dic[s]
        dfs()
        return 'Bob' if total > 2 * dic[0] else 'Alice' if total < 2 * dic[0] else 'Tie'

from functools import lru_cache
class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        c=0
        sums=[]
        for i in range(len(stoneValue)-1,-1,-1):
            c+=stoneValue[i]
            sums.append(c)
        
        @lru_cache(None)
        def optimalValue(s):
            if not s:
                return 0
            return max([sums[s-1]-optimalValue(s-i) for i in range(1,4) if s-i>=0])
        half=0.5*sum(stoneValue)
        res=optimalValue(len(stoneValue))
        return 'Alice' if res>half else 'Bob' if res<half else 'Tie'


class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        dp = [float('-inf')]*len(stoneValue)
        self.presum = [0]*(len(stoneValue) + 1)
        for idx, num in enumerate(stoneValue[::-1]):
            self.presum[len(stoneValue) - idx - 1] = self.presum[len(stoneValue) - idx] + num
        self.presum.pop()
        
        alice_score = self.helper(stoneValue, 0, dp)
        if alice_score > sum(stoneValue) - alice_score:
            return 'Alice'
        elif alice_score < sum(stoneValue) - alice_score:
            return 'Bob'
        else:
            return 'Tie'
    
    def helper(self, nums, start, dp):
        if dp[start] != float('-inf'):
            return dp[start]
        
        if start == len(nums) - 1:
            dp[start] = nums[start]
            return nums[start]
        
        if start == len(nums) - 2:
            dp[start] = max(self.presum[start], nums[start])
            return dp[start]
        
        if start == len(nums) - 3:
            dp[start] = max(self.presum[start], self.presum[start] - self.helper(nums, start + 1, dp), self.presum[start] - self.helper(nums, start + 2, dp))
            return dp[start]
        
        num1 = self.presum[start] - self.helper(nums, start + 1, dp)
        num2 = self.presum[start] - self.helper(nums, start + 2, dp) if start + 2 < len(nums) else float('-inf')
        num3 = self.presum[start] - self.helper(nums, start + 3, dp) if start + 3 < len(nums) else float('-inf')
        dp[start] = max(num1, num2, num3)
        return dp[start]

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        # aliceScore = [0]
        # bobScore = [0]
        # INVALID = 's'
        # def helper(stoneValues,index,aliceScore,bobScore,aliceTurn):
        #     scoreToUpdate = aliceScore
        #     if not aliceTurn:
        #         scoreToUpdate = bobScore
        #     if len(stoneValues) - 1 == index:
        #         scoreToUpdate[0] += stoneValues[index]
        #         return
        #     bck = scoreToUpdate[0]
        #     sums = []
        #     for i in range(1,4):
        #         scoreToUpdate[0] = bck
        #         if i + index <= len(stoneValues):
        #             for j in range(i):
        #                 scoreToUpdate[0] += stoneValues[index+j]
        #             helper(stoneValues,index + i,aliceScore,bobScore,not aliceTurn)
        #             sums.append(scoreToUpdate[0])
        #     if len(sums) > 0:
        #         scoreToUpdate[0] = max(sums)
        #     else:
        #         scoreToUpdate[0] = bck
        #     return
        # helper(stoneValue,0,aliceScore,bobScore,True)
        # if aliceScore[0] > bobScore[0]:
        #     return 'Alice'
        # elif bobScore[0] > aliceScore[0]:
        #     return 'Bob'
        # return 'Tie'
        # def helper(stoneValues,index):
        #     if index in mem:
        #         return mem[index]
        #     if index >= len(stoneValues):
        #         return 0
        #     ans = stoneValues[index] - helper(stoneValues,index+1)
        #     if index + 1 < len(stoneValues):
        #         temp = stoneValues[index] + stoneValues[index+1] - helper(stoneValues,index+2)
        #         ans = max(ans,temp)
        #     if index + 2 < len(stoneValues):
        #         temp = stoneValues[index] + stoneValues[index+1] + stoneValues[index+2] - helper(stoneValues,index+3)
        #         ans = max(ans,temp)
        #     mem[index] = ans
        #     return ans
        # ans = helper(stoneValue,0)
        mem = {i:0 for i in range(len(stoneValue)+1)}
        mem1, mem2, mem3 = 0, 0, 0
        i = len(stoneValue) - 1
        while i >= 0:
            ans = stoneValue[i] - mem1
            if i + 1 < len(stoneValue):
                ans = max(ans,stoneValue[i] + stoneValue[i+1] - mem2)
            if i + 2 < len(stoneValue):
                 ans = max(ans,stoneValue[i] + stoneValue[i+1] + stoneValue[i+2] - mem3)
            mem3 = mem2
            mem2 = mem1
            mem1 = ans
            i -= 1
        if ans > 0:
            return 'Alice'
        elif ans < 0:
            return 'Bob'
        return 'Tie'

class Solution:
    def stoneGameIII(self, stones: List[int]) -> str:
        n = len(stones)
        dp = [-math.inf] * (n + 1)
        dp[n] = 0
        for i in range(n - 1, -1, -1):
            take = 0
            for j in range(i + 1, min(i + 3, n) + 1):
                take += stones[j - 1]
                dp[i] = max(dp[i], take - dp[j])
        return 'Alice' if dp[0] > 0 else 'Bob' if dp[0] < 0 else 'Tie'



class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        @lru_cache(maxsize=None)
        def solve(i: int) -> int:
            if i >= len(stoneValue):
                return 0
            
            res = -math.inf
            for stones in range(1, 4):
                curr_val = sum(stoneValue[i: i + stones]) + min(solve(i + stones + 1), solve(i + stones + 2), solve(i + stones + 3))
                res = max(res, curr_val)
            
            return res
        
        alice = solve(0)
        bob = sum(stoneValue) - alice
        if alice == bob:
            return 'Tie'
        elif alice > bob:
            return 'Alice'
        else:
            return 'Bob'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        self.cache = [0] * 50001
        total = sum(stoneValue)
        first = (total + self.helper(stoneValue, 0)) // 2
        second = total - first
        if first > second:
            return 'Alice'
        elif first < second:
            return 'Bob'
        else:
            return 'Tie'
    
    def helper(self, stoneValue, index):
        if self.cache[index]:
            return self.cache[index]
        
        n = len(stoneValue)
        if index == n:
            return 0

        if index == n - 1:
            return stoneValue[-1]
        
        cur = 0
        best = -sys.maxsize
        for i in range(3):
            if index + i >= n:
                break
            
            cur += stoneValue[index + i]
            best = max(best, cur - self.helper(stoneValue, index + i + 1))
        
        self.cache[index] = best
        return best


from functools import lru_cache


class Solution:
    def stoneGameIII(self, s: List[int]) -> str:
        nums = len(s)
        
        @lru_cache(None)
        def helper(index, first):
            r = nums - index
            
            if r == 0:
                return 0, 0

            if r == 1:
                if first:
                    return s[-1], 0
                else:
                    return 0, s[-1]
            
            if r == 2:
                x, y = s[-2:]
                if 0 <= x and 0 <= y or x < 0 and y > 0:
                    if first:
                        return x+y, 0
                    return 0, x+y
                if first:
                    return x, y
                return y, x
            
            a1, b1 = helper(index+1, not first)
            a2, b2 = helper(index+2, not first)
            a3, b3 = helper(index+3, not first)
            
            if first:
                a1 += s[index]
                a2 += sum(s[index:index+2])
                a3 += sum(s[index:index+3])
            else:
                b1 += s[index]
                b2 += sum(s[index:index+2])
                b3 += sum(s[index:index+3])
            
            choices = [(a1, b1), (a2, b2), (a3, b3)]
            if first:
                return max(choices)
            return min(choices)
        
        a, b = helper(0, True)
        if a == b:
            return 'Tie'
        if a < b:
            return 'Bob'
        return 'Alice'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        numStones = len(stoneValue)
        dp = [-float('inf')] * numStones
        for i in range(numStones - 1, -1, -1):
            localTotal = 0
            for j in range(i, min(i+3, numStones)):
                localTotal += stoneValue[j]
                otherPlayerMax = dp[j+1] if j+1 < numStones else 0
                dp[i] = max(dp[i], localTotal - otherPlayerMax)
        #print(dp)
        winner = 'Alice' if dp[0] > 0 else 'Bob' if dp[0] < 0 else 'Tie'
        return winner
                


from functools import lru_cache


class Solution:
    def stoneGameIII(self, s: List[int]) -> str:
        nums = len(s)
        
        @lru_cache(maxsize=10000)
        def helper(index, first):
            r = nums - index
            
            if r == 0:
                return 0, 0

            if r == 1:
                if first:
                    return s[-1], 0
                else:
                    return 0, s[-1]
            
            if r == 2:
                x, y = s[-2:]
                if 0 <= x and 0 <= y or x < 0 and y > 0:
                    if first:
                        return x+y, 0
                    return 0, x+y
                if first:
                    return x, y
                return y, x
            
            a1, b1 = helper(index+1, not first)
            a2, b2 = helper(index+2, not first)
            a3, b3 = helper(index+3, not first)
            
            if first:
                a1 += s[index]
                a2 += sum(s[index:index+2])
                a3 += sum(s[index:index+3])
            else:
                b1 += s[index]
                b2 += sum(s[index:index+2])
                b3 += sum(s[index:index+3])
            
            choices = [(a1, b1), (a2, b2), (a3, b3)]
            if first:
                return max(choices)
            return min(choices)
        
        a, b = helper(0, True)
        if a == b:
            return 'Tie'
        if a < b:
            return 'Bob'
        return 'Alice'

from functools import lru_cache

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        vals = stoneValue
        n = len(vals)
        @lru_cache(None)
        def play(i):
            if i == n:
                return 0, 0
            p1, p2 = -1e9, -1
            s = 0
            for j in range(i, min(i + 3, n)):
                s += vals[j]
                p1_, p2_ = play(j + 1)
                p2_ += s
                if p2_ > p1:
                    p1 = p2_
                    p2 = p1_
            return p1, p2
        
        p1, p2 = play(0)
        # print(p1, p2)
        # p2 = sum(vals) - p1
        if p1 > p2:
            return 'Alice'
        elif p1 == p2:
            return 'Tie'
        return 'Bob'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        dp = {}
        total = sum(stoneValue)
        def help(start, s):
            if start in dp: return dp[start]
            if start >= len(stoneValue): return 0
            dp[start] = max(s - help(start+1, s-stoneValue[start]), s- help(start+2,s-sum(stoneValue[start:start+2])), s-help(start+3,s-sum(stoneValue[start: start+3])))
            return dp[start]
        
        
        A = help(0, total)
       
        if 2*A > total: return 'Alice'
        elif 2*A == total: return 'Tie'
        else: return 'Bob'

from functools import lru_cache
class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        @lru_cache(None)
        def getScore(idx,aliceNext):#score = Alice-Bob
            if idx==n:
                return 0
            if aliceNext:
                res=-float('inf')
                t=0
                for i in range(3):
                    if idx+i==n:
                        break
                    t+=values[idx+i]
                    res=max(res,t+getScore(idx+i+1,False))
                return res
            else:
                res=float('inf')
                t=0
                for i in range(3):
                    if idx+i==n:
                        break
                    t+=values[idx+i]
                    res=min(res,-t+getScore(idx+i+1,True))
                return res
        values=stoneValue            
        n=len(values)
        for i in range(n-1,-1,-1):
            getScore(i,True)
            getScore(i,False)
        
        ans=getScore(0,True)
        
        ans2='Tie'
        if ans>0:
            ans2='Alice'
        if ans<0:
            ans2='Bob'
        return ans2

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        from functools import lru_cache
        @lru_cache(None)
        def dp(index, my_turn):
            if index >= len(stoneValue):
                return 0
            if my_turn:
                rst = float('-inf')
                for i in range(3):
                    rst = max(rst, sum(stoneValue[index:index+i+1]) + dp(index+i+1, False))
                return rst
            
            rst = float('inf')
            for i in range(3):
                rst = min(rst, dp(index+i+1, True))
            return rst
        
        score = dp(0, True) * 2
        if score < sum(stoneValue):
            return 'Bob'
        if score == sum(stoneValue):
            return 'Tie'
        return 'Alice'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        firstSelect = True  # True denoted Alice select first, False for Bob
        initIndex = 0
        stoneValueLength = len(stoneValue)
        mem = {}

        if stoneValueLength == 0:
            return 'Tie'
        else:
            result = self.recursiveHelper(stoneValue, stoneValueLength, initIndex, firstSelect, mem)
            #print(result)
            if result > 0:
                return 'Alice'
            elif result < 0:
                return 'Bob'
            else:
                return 'Tie'

    def recursiveHelper(self, stoneValue: List[int], length: int, index: int, flag: bool, mem: dict) -> int:

        if index >= length:
            return 0

        memV = mem.get((index, flag))
        if memV is not None:
            return memV

        minus = length - index
        if minus == 1:  # only one choice
            curr = stoneValue[index]
            c1 = curr if flag else -curr
            mem[(index, flag)] = c1
            return c1
        elif minus == 2:  # two choices
            # 1 select all two
            curr = stoneValue[index] + stoneValue[index + 1]
            c1 = curr if flag else -curr

            # 2 select the first one
            curr = stoneValue[index]
            c2 = (curr if flag else -curr) + self.recursiveHelper(stoneValue, length, index + 1, not flag, mem)

            result = max(c1, c2) if flag else min(c1, c2)
            mem[(index, flag)] = result
            return result
        else:  # >= 3; three choices
            # 1 select all three
            curr = stoneValue[index] + stoneValue[index + 1] + stoneValue[index + 2]
            c1 = (curr if flag else -curr) + self.recursiveHelper(stoneValue,length, index + 3, not flag, mem)

            # 2 select the first two
            curr = stoneValue[index] + stoneValue[index + 1]
            c2 = (curr if flag else -curr) + self.recursiveHelper(stoneValue, length, index + 2, not flag, mem)

            # 3 select the first one
            curr = stoneValue[index]
            c3 = (curr if flag else -curr) + self.recursiveHelper(stoneValue, length, index + 1, not flag, mem)
            result = max(c1, c2, c3) if flag else min(c1, c2, c3)
            mem[(index, flag)] = result
            return result


class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        @lru_cache(None)
        def dp(i, t):
            if i == len(stoneValue):
                return 0
            if t == 0:
                m = -math.inf
                s = 0
                for j in range(i, min(i+3, len(stoneValue))):
                    s += stoneValue[j]
                    m = max(m, s + dp(j+1, 1))
            else:
                m = math.inf
                s = 0
                for j in range(i, min(i+3, len(stoneValue))):
                    s -= stoneValue[j]
                    m = min(m, s + dp(j+1, 0))
            return m
        
        ans = dp(0, 0)
        if ans > 0:
            return 'Alice'
        elif ans < 0:
            return 'Bob'
        else:
            return 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        self.cache = {}
        score = self.solve(0, stoneValue)
        return 'Alice' if score > 0 else 'Bob' if score < 0 else 'Tie'
    

    def solve(self, s, stoneValue): # score diff
        n = len(stoneValue)
        if s>=n: 
            return 0

        if s in self.cache: 
            return self.cache[s]

        best = -2**31
        presum = 0

        for x in range(1, 4):
            if s+x-1>=n:
                break
            presum += stoneValue[s+x-1]
            best = max(best, presum - self.solve(s+x, stoneValue)) # min-max process
        self.cache[s] = best
        return best
    
    
    
    


class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        ts = sum(stoneValue)
        n = len(stoneValue)
        
        a = [0 for i in range(n)]
        for i in range(n-1, -1, -1):
            if i == n-1:
                a[i] = stoneValue[i]
            else:
                a[i] = a[i+1] + stoneValue[i]
        
        cache = {}
        def process(i):
            if i == n:
                return 0
            else:
                if not i in cache:
                    ans = -float('inf')
                    if i < n:
                        ans = max(ans, stoneValue[i] + (a[i+1] - process(i+1) if i+1 < n else 0))
                    if i+1 < n:
                        ans = max(ans, stoneValue[i]+stoneValue[i+1] + (a[i+2] - process(i+2) if i+2 < n else 0))
                    if i+2 < n:
                        ans = max(ans, stoneValue[i]+stoneValue[i+1]+stoneValue[i+2] + (a[i+3] - process(i+3) if i+3 < n else 0))
                    cache[i] = ans
                return cache[i]
        
        Alice = process(i)
        Bob = ts - Alice
        if Alice > Bob:
            return 'Alice'
        elif Bob > Alice:
            return 'Bob'
        else:
            return 'Tie'


from functools import lru_cache
class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        @lru_cache(None)
        def getScore(idx,aliceNext):#score = Alice-Bob
            if idx==n:
                return 0
            if aliceNext:
                res=-float('inf')
                t=0
                for i in range(3):
                    if idx+i==n:
                        break
                    t+=values[idx+i]
                    res=max(res,t+getScore(idx+i+1,False))
                return res
            else:
                res=float('inf')
                t=0
                for i in range(3):
                    if idx+i==n:
                        break
                    t+=values[idx+i]
                    res=min(res,-t+getScore(idx+i+1,True))
                return res
        values=stoneValue            
        n=len(values)
        ans=getScore(0,True)
        
        ans2='Tie'
        if ans>0:
            ans2='Alice'
        if ans<0:
            ans2='Bob'
        return ans2

class Solution:
    def stoneGameIII(self, stoneValue) -> str:
        total_value = sum(stoneValue)
        num_stones = len(stoneValue)
        
        @lru_cache(None)
        def helper(ind, player):
            if ind >= num_stones:
                return 0
            
            if player == 'A': # Alex as the player
                tmp_result = []
                for i in range(1, 4):
                    if ind + i <= num_stones:
                        tmp_result.append( sum(stoneValue[ind: ind+i]) + helper(ind+i, 'L')  )
                    else:
                        tmp_result.append( sum(stoneValue[ind: ]) + helper(num_stones, 'L')  )
                return max(tmp_result)
            elif player == 'L':
                tmp_result = []
                for i in range(1, 4):
                    if ind + i <= num_stones:
                        tmp_result.append(helper(ind+i, 'A')  )
                    else:
                        tmp_result.append(helper(num_stones, 'A')  )
                    
                return min(tmp_result)
        
        alex_score = helper(0, 'A')
        
        if alex_score > total_value / 2.:
            return 'Alice'
        elif alex_score < total_value / 2.:
            return 'Bob'
        else:
            return 'Tie'

from functools import lru_cache


class Solution:
    def stoneGameIII(self, s: List[int]) -> str:
        nums = len(s)
        memo = {}
        
        def helper(index, first):
            if (index, first) in memo:
                return memo[index, first]
            
            r = nums - index
            
            if r == 0:
                return 0, 0

            if r == 1:
                if first:
                    return s[-1], 0
                else:
                    return 0, s[-1]
            
            if r == 2:
                x, y = s[-2:]
                if 0 <= x and 0 <= y or x < 0 and y > 0:
                    if first:
                        return x+y, 0
                    return 0, x+y
                if first:
                    return x, y
                return y, x
            
            a1, b1 = helper(index+1, not first)
            a2, b2 = helper(index+2, not first)
            a3, b3 = helper(index+3, not first)
            
            if first:
                a1 += s[index]
                a2 += sum(s[index:index+2])
                a3 += sum(s[index:index+3])
            else:
                b1 += s[index]
                b2 += sum(s[index:index+2])
                b3 += sum(s[index:index+3])
            
            choices = [(a1, b1), (a2, b2), (a3, b3)]
            if first:
                ans = max(choices)
            else:
                ans = min(choices)
            
            memo[index, first] = ans
            return ans
        
        a, b = helper(0, True)
        if a == b:
            return 'Tie'
        if a < b:
            return 'Bob'
        return 'Alice'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        if not stoneValue:
            return 'Tie'
        
        pre_sum = [0 for _ in range(len(stoneValue) + 1)]
        for i in range(len(stoneValue)):
            pre_sum[i+1] = pre_sum[i] + stoneValue[i]
        
        @lru_cache(None)
        def dfs(idx, player):
            if idx > len(stoneValue) - 1:
                return 0
            if player == 1:
                res = float('-inf')
                for i in range(1, 4):
                    # Take 1, 2, 3 stones from head.
                    if idx + i > len(stoneValue):
                        break
                    res = max(res, pre_sum[idx + i] - pre_sum[idx] + dfs(idx + i, -player))
            else:
                res = float('inf')
                for i in range(1, 4):
                    res = min(res, dfs(idx+i, -player))
            
            return res
        
        a_sum = dfs(0, 1)
        b_sum = pre_sum[-1] - a_sum
        
        if a_sum == b_sum:
            return 'Tie'
        elif a_sum > b_sum:
            return 'Alice'
        else:
            return 'Bob'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        memo = {}
        
        def dfs(i, bob):
            if (i, bob) in memo:
                return memo[i, bob]
            
            if i >= n:
                return 0
            
            ans = float('inf') if bob else float('-inf')
            for x in [1, 2, 3]:
                sub = dfs(i + x, 1 - bob)
                if bob: 
                    ans = min(ans, sub)     # minimize what alex get
                else:
                    ans = max(ans, sub + sum(stoneValue[i:i + x]))
            
            memo[i, bob] = ans
            return ans
        
        
        dfs(0, 0)
        dfs(0, 1)
        if memo[0, 1] == memo[0, 0]:
            return 'Tie'
        
        return 'Bob' if memo[0, 1] > memo[0, 0] else 'Alice'


class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        
        stoneN = len(stoneValue)
        totalScore = sum(stoneValue)
        
        dp = {}
        
        def play(i0, ARound):
            if i0 == stoneN:
                return 0
            if (i0, ARound) in dp:
                return dp[(i0, ARound)]
            if ARound:
                subAns = float('-inf')
                thisRoundScore = 0
                for j in range(i0, min(i0+3, stoneN)):
                    thisRoundScore += stoneValue[j]
                    subAns = max(subAns, thisRoundScore + play(j+1, False))
            else:
                subAns = float('inf')
                for j in range(i0, min(i0+3, stoneN)):
                    subAns = min(subAns, play(j+1, True))
            
            dp[(i0, ARound)] = subAns
            return subAns
        
        aScore = play(0, True) 
        bScore = totalScore - aScore
        # print(aScore, bScore)
        
        if aScore == bScore:
            return 'Tie'
        elif aScore > bScore:
            return 'Alice'
        else:
            return 'Bob'
        
#         AliceWinDict = {}
#         TieDict = {}
#         BobWinDict = {}
#         dp = {}
        
#         def play(i0, ARound, aScore, bScore):
#             if i0 == stoneN:
#                 if aScore == bScore:
#                     return 'Tie'
#                 elif aScore > bScore:
#                     return 'Alice'
#                 else:
#                     return 'Bob'
            
#             if (i0, ARound, aScore, bScore) in dp:
#                 return dp[(i0, ARound, aScore, bScore)]
            
#             if (i0, ARound) in TieDict:
#                 if aScore > TieDict[(i0, ARound)]:
#                     ans = 'Alice'
#                 elif aScore < TieDict[(i0, ARound)]:
#                     ans = 'Bob'
#                 return 'Tie'
#                 # ans = 'Tie'
#             else:
            
#                 if (i0, ARound) in AliceWinDict:
#                     if aScore >= AliceWinDict[(i0, ARound)]:
#                         return 'Alice'

#                 if (i0, ARound) in BobWinDict:
#                     if bScore >= BobWinDict[(i0, ARound)]:
#                         return 'Bob'

#                 if ARound:
#                     ans = None
#                     thisRoundScore = 0
#                     for j in range(i0, min(i0+3, stoneN)):
#                         thisRoundScore += stoneValue[j]
#                         subAns = play(j+1, False, aScore + thisRoundScore, bScore)

#                         if subAns == 'Alice':
#                             ans = 'Alice'
#                             break
#                         elif subAns == 'Tie':
#                             if ans == None:
#                                 ans = 'Tie'
#                     if ans == None:
#                         ans = 'Bob'
#                 else:
#                     ans = None
#                     thisRoundScore = 0
#                     for j in range(i0, min(i0+3, stoneN)):
#                         thisRoundScore += stoneValue[j]
#                         subAns = play(j+1, True, aScore, bScore + thisRoundScore)
#                         if subAns == 'Bob':
#                             ans = 'Bob'
#                             break
#                         elif subAns == 'Tie':
#                             if ans == None:
#                                 ans = 'Tie'
#                     if ans == None:
#                         ans = 'Alice'
                    
#             if ans == 'Tie':
#                 TieDict[(i0, ARound)] = aScore
                
#             elif ans == 'Alice':
#                 if (i0, ARound) in AliceWinDict:
#                     AliceWinDict[(i0, ARound)] = min(aScore, AliceWinDict[(i0, ARound)])
#                 else:
#                     AliceWinDict[(i0, ARound)] = aScore
                    
#             elif ans == 'Bob':
#                 if (i0, ARound) in BobWinDict:
#                     BobWinDict[(i0, ARound)] = min(bScore, BobWinDict[(i0, ARound)])
#                 else:
#                     BobWinDict[(i0, ARound)] = bScore   
                    
#             dp[(i0, ARound, aScore, bScore)] = ans
#             return ans
        
#         return play(0, True, 0, 0)


class Solution:
    def stoneGameIII(self, cards):
        dp = [float('-inf')]*(len(cards))
        
        for i in range(len(dp)-1,-1, -1):
            if len(dp)-1 - i >= 3:
                dp[i] = max(sum(cards[i:i+3]) - dp[i+3], sum(cards[i:i+2]) - dp[i+2], sum(cards[i:i+1]) - dp[i+1])
            elif len(dp)-1 - i == 2:
                dp[i] = max(sum(cards[i:i+3]), sum(cards[i:i+2]) - dp[i+2], sum(cards[i:i+1]) - dp[i+1])
            elif len(dp)-1 - i == 1:
                dp[i] = max(sum(cards[i:i+2]), sum(cards[i:i+1]) - dp[i+1])
            elif len(dp)-1 - i == 0:
                dp[i] = cards[i]
        print(dp)
        if dp[0] >0:
            return 'Alice'
        elif dp[0] < 0:
            return 'Bob'
        else:
            return 'Tie'

class Solution:
    def stoneGameIII(self, cards):
        lookup = {}
        val = self.scoreGivenCards(cards, 0, True, lookup)
        result =  val - sum(cards)/2
        if result > 0:
            return 'Alice'
        elif result < 0:
            return 'Bob'
        else:
            return 'Tie'

    def scoreGivenCards(self, cards, index, is_it_your_turn, lookup):
        if index >= len(cards):
            return 0    
        if is_it_your_turn:
            # pick 1
            if (index + 1, not is_it_your_turn) not in lookup:
                lookup[(index + 1, not is_it_your_turn)] = self.scoreGivenCards(cards, index + 1, not is_it_your_turn, lookup)
            score_with_one = cards[index] + lookup[(index + 1, not is_it_your_turn)]
            # pick 2
            if (index + 2, not is_it_your_turn) not in lookup:
                lookup[(index + 2), not is_it_your_turn] = self.scoreGivenCards(cards, index + 2, not is_it_your_turn, lookup)
            score_with_two = sum(cards[index:index+2]) +  lookup[(index + 2, not is_it_your_turn)]
            # pick 3
            if (index + 3, not is_it_your_turn) not in lookup:
                lookup[(index + 3, not is_it_your_turn)] = self.scoreGivenCards(cards, index + 3, not is_it_your_turn, lookup)
            score_with_three = sum(cards[index:index+3]) +  lookup[(index + 3, not is_it_your_turn)]
            return max(score_with_one, score_with_two, score_with_three)
        else:
            # pick 1
            if (index + 1, not is_it_your_turn) not in lookup:
                lookup[(index + 1, not is_it_your_turn)] = self.scoreGivenCards(cards, index + 1, not is_it_your_turn, lookup)
            score_with_one = lookup[(index + 1, not is_it_your_turn)]
            # pick 2
            if (index + 2, not is_it_your_turn) not in lookup:
                lookup[(index + 2, not is_it_your_turn)] = self.scoreGivenCards(cards, index + 2, not is_it_your_turn, lookup)
            score_with_two = lookup[(index + 2, not is_it_your_turn)]
            # pick 3
            if (index + 3, not is_it_your_turn) not in lookup:
                lookup[(index + 3, not is_it_your_turn)] = self.scoreGivenCards(cards, index + 3, not is_it_your_turn, lookup)
            score_with_three = lookup[(index + 3, not is_it_your_turn)]
            return min(score_with_one, score_with_two, score_with_three)

class Solution:
    def stoneGameIII(self, S: List[int]) -> str:
        
        n = len(S)
        
        dp = [0] * n
        
        for i in range(n)[::-1]:
            for k in range(1, 4):
                dp[i] =  max(sum(S[i:i+k]) - (dp[i+k] if i + k < n else 0) for k in (1,2,3)  )
            
        
        if dp[0] > 0:
            return 'Alice'
        elif dp[0] < 0:
            return 'Bob'
        else:
            return 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        presum = [0]
        for num in stoneValue:
            presum.append(presum[-1] + num)
        
        @lru_cache(None)
        def dfs(i):
            if i >= len(stoneValue):
                return 0
            ans = float('-inf')
            temp = 0
            for k in range(3):
                if i + k < len(stoneValue):
                    temp += stoneValue[i + k]
                    remain = presum[-1] - presum[i + k + 1]
                    ans = max(ans, temp + remain - dfs(i + k + 1))
                    
            return  ans
            
        total = dfs(0)
        if total * 2 > presum[-1]:
            return 'Alice'
        elif total * 2 < presum[-1]:
            return 'Bob'
        else:
            return 'Tie'

class Solution:
    def stoneGameIII(self, stones: List[int]) -> str:
        n = len(stones)
        memo = {}
        def solve(i):
            if i == n:
                return 0
            if i in memo:
                return memo[i]
            ans, curr = -math.inf, 0
            for j in range(i, min(n, i+3)):
                curr += stones[j]
                ans = max(ans, curr-solve(j+1))
            memo[i] = ans
            return ans
        score = solve(0)
        if score > 0:
            return 'Alice'
        elif score < 0:
            return 'Bob'
        else:
            return 'Tie'


from functools import lru_cache


class Solution:
    def stoneGameIII(self, s: List[int]) -> str:
        nums = len(s)
        memo = {}
        
        def helper(index, first):
            r = nums - index
            
            if r == 0:
                return 0, 0

            if r == 1:
                if first:
                    return s[-1], 0
                else:
                    return 0, s[-1]
            
            if r == 2:
                x, y = s[-2:]
                if 0 <= x and 0 <= y or x < 0 and y > 0:
                    if first:
                        return x+y, 0
                    return 0, x+y
                if first:
                    return x, y
                return y, x
            
            if (index, first) in memo:
                return memo[index, first]
            
            a1, b1 = helper(index+1, not first)
            a2, b2 = helper(index+2, not first)
            a3, b3 = helper(index+3, not first)
            
            if first:
                a1 += s[index]
                a2 += sum(s[index:index+2])
                a3 += sum(s[index:index+3])
            else:
                b1 += s[index]
                b2 += sum(s[index:index+2])
                b3 += sum(s[index:index+3])
            
            choices = [(a1, b1), (a2, b2), (a3, b3)]
            if first:
                ans = max(choices)
            else:
                ans = min(choices)
            
            memo[index, first] = ans
            return ans
        
        a, b = helper(0, True)
        if a == b:
            return 'Tie'
        if a < b:
            return 'Bob'
        return 'Alice'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        @lru_cache(None)
        def dp(i,chance):
            n = len(stoneValue)
            if i >= len(stoneValue):
                return 0
            
            if not chance:
                ans = float('-inf')
                for j in range(i,i+3):
                    if j < n:
                        ans = max(ans, dp(j+1,1)+sum(stoneValue[i:j+1]))
                
            else:
                ans = float('inf')
                for j in range(i,i+3):
                    if j < n:
                        ans = min(ans, dp(j+1,0)-sum(stoneValue[i:j+1]))
            return ans
        
        score = dp(0,0)
        if score > 0:
            return 'Alice'
        if score < 0:
            return 'Bob'
        return 'Tie'

class Solution:
    def stoneGameIII(self, piles: List[int]) -> str:
        N = len(piles)

        @lru_cache(None)
        def sg(idx,turn):

            if idx == N:
                return 0

            res = float('-inf')

            if turn == -1:
                res = float('inf')

            ps = 0

            for i in range(idx,min(idx+3, N)):
                ps += piles[i]

                nxt = (ps * turn) + sg(i+1,-turn)

                if turn == 1:
                    res = max(res,nxt)
                else:
                    res = min(res,nxt)

            return res

        res = sg(0,1)

        if res > 0:
            return 'Alice'
        elif res < 0:
            return 'Bob'

        return 'Tie'        

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        # dont take the below, because it can be negative, [-1,-2,-3]
        #if len(stoneValue) <= 3:
        #    return 'Alice'
        p1, p2, p3 = 0, 0, 0
        post_sum = 0
        for i in range(len(stoneValue) - 1, -1, -1):
            val = stoneValue[i]
            post_sum += val
            best = post_sum - min([p1, p2, p3])
            p1, p2, p3 = best, p1, p2
        if p1 > post_sum - p1:
            return 'Alice'
        elif p1 < post_sum - p1:
            return 'Bob'
        else:
            return 'Tie'

from functools import lru_cache

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        vals = stoneValue
        n = len(vals)
        dp = collections.deque([None] * 3)
        dp[0] = [0, 0]
        for i in range(n - 1, -1, -1):
            s = vals[i]
            p1, p2 = dp[0][1] + s, dp[0][0]
            for j in range(i + 1, min(i + 3, n)):
                s += vals[j]
                p1_, p2_ = dp[j - i]
                p2_ += s
                if p2_ > p1:
                    p1 = p2_
                    p2 = p1_
            dp.pop()
            dp.appendleft((p1, p2))
        
        p1, p2 = dp[0]
        if p1 > p2:
            return 'Alice'
        elif p1 == p2:
            return 'Tie'
        return 'Bob'

class Solution:
    def stoneGameIII(self, stones: List[int]) -> str:
        rowlen=len(stones)
        #dp=[0] * (rowlen+1)
        i=rowlen-1
        i_1,i_2,i_3=0,0,0
        
        
        while i >= 0:
            
            answer=-float('inf')
            
            answer=max(answer,stones[i] - i_1)
            
            if i+1 < rowlen:
                answer=max(answer,stones[i]+stones[i+1] - i_2)  
                
            if i+2 < rowlen:
                answer=max(answer,stones[i]+stones[i+1]+stones[i+2] - i_3)
        
            i_3=i_2
            i_2=i_1
            i_1 = answer 
            i-=1
            
        if i_1 > 0:
            return 'Alice'
        elif i_1 < 0:
            return 'Bob'
        else:
            return 'Tie'
        
        
        
        
        '''
        # Recursion + TopDown
        rowlen=len(stones)
        index=0
        memo=[-1] * rowlen
             
        def helper(index,memo):
            
            if index >= rowlen:
                return 0
            elif memo[index] != -1:
                return memo[index] 
            else:
                answer=-float('inf')
                answer=max(answer,stones[index] - helper(index+1,memo))
                if index + 1 < rowlen:
                    answer=max(answer,stones[index]+stones[index+1] - helper(index+2,memo))
                
                if index + 2 < rowlen:
                    answer=max(answer,stones[index]+stones[index+1]+stones[index+2] - helper(index+3,memo))
                
                memo[index]=answer
                return memo[index]      
                
        answer=helper(0,memo)
        print(answer)
        
        if answer < 0:
            return 'Bob'
        elif answer > 0:
            return 'Alice'
        else:
            return 'Tie'
            
        '''      

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        
        i = n - 1
        
        i1, i2, i3 = 0, 0, 0
        
        while i>=0:
            ans = float('-inf')
            
            ans = max(ans, stoneValue[i] - i1)
            
            if i+1 < n:
                ans = max(ans, stoneValue[i] + stoneValue[i+1] - i2)
                
            if i+2 < n:
                ans = max(ans, stoneValue[i] + stoneValue[i+1] + stoneValue[i+2] - i3)
                
            i3 = i2
            i2 = i1
            i1 = ans
            i -= 1
        
        if i1 > 0:
            return 'Alice'
        elif i1 < 0:
            return 'Bob'
        return 'Tie'

class Solution:
    def stoneGameIII(self, s: List[int]) -> str:
        i_1 = i_2 = i_3 = 0
        i = len(s)-1
        while i>=0:
            ans = -sys.maxsize
            ans = max(ans, s[i] - i_1)
            if i+1 < len(s):
                ans = max(ans, s[i]+s[i+1] - i_2)
            if i+2 < len(s):
                ans = max(ans, s[i]+s[i+1]+s[i+2] - i_3)
            i_3 = i_2
            i_2 = i_1
            i_1 = ans
            i -= 1
            
        a = i_1
        if a > 0:
            return 'Alice'
        if a == 0:
            return 'Tie'
        return 'Bob'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        dp = [-2**31]*n # max diff points Alice can win over Bob
        for i in range(n-1, -1, -1):
            take = 0
            for j in range(i, min(i+3, n)):
                take += stoneValue[j]
                dp[i] = max(dp[i], take - (dp[j+1] if j+1 < n else 0))
        
        if dp[0] > 0:
            return 'Alice'
        elif dp[0] < 0:
            return 'Bob'
        else:
            return 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        # time complexity: O(N)
        # space complexity: O(N)
        N = len(stoneValue)
        stoneValue += [0, 0, 0]        
        dp = [-sys.maxsize] * N + [0, 0, 0]
        for i in range(N-1, -1, -1):
            for k in (1,2,3):
                dp[i] = max(dp[i], sum(stoneValue[i:i+k]) - dp[i+k])
        if dp[0] > 0: return 'Alice'
        elif dp[0] < 0: return 'Bob'
        else: return 'Tie'


from functools import lru_cache
class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        @lru_cache(maxsize=None)
        def score(i):
            if i >= N: return 0
            return max(stoneValue[i] - score(i+1),
                   sum(stoneValue[i:i+2]) - score(i+2),
                   sum(stoneValue[i:i+3]) - score(i+3))
        N = len(stoneValue)
        s = score(0)
        if s > 0: return 'Alice'
        elif s < 0: return 'Bob'
        else: return 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        # aliceScore = [0]
        # bobScore = [0]
        # INVALID = 's'
        # def helper(stoneValues,index,aliceScore,bobScore,aliceTurn):
        #     scoreToUpdate = aliceScore
        #     if not aliceTurn:
        #         scoreToUpdate = bobScore
        #     if len(stoneValues) - 1 == index:
        #         scoreToUpdate[0] += stoneValues[index]
        #         return
        #     bck = scoreToUpdate[0]
        #     sums = []
        #     for i in range(1,4):
        #         scoreToUpdate[0] = bck
        #         if i + index <= len(stoneValues):
        #             for j in range(i):
        #                 scoreToUpdate[0] += stoneValues[index+j]
        #             helper(stoneValues,index + i,aliceScore,bobScore,not aliceTurn)
        #             sums.append(scoreToUpdate[0])
        #     if len(sums) > 0:
        #         scoreToUpdate[0] = max(sums)
        #     else:
        #         scoreToUpdate[0] = bck
        #     return
        # helper(stoneValue,0,aliceScore,bobScore,True)
        # if aliceScore[0] > bobScore[0]:
        #     return 'Alice'
        # elif bobScore[0] > aliceScore[0]:
        #     return 'Bob'
        # return 'Tie'
        # def helper(stoneValues,index):
        #     if index in mem:
        #         return mem[index]
        #     if index >= len(stoneValues):
        #         return 0
        #     ans = stoneValues[index] - helper(stoneValues,index+1)
        #     if index + 1 < len(stoneValues):
        #         temp = stoneValues[index] + stoneValues[index+1] - helper(stoneValues,index+2)
        #         ans = max(ans,temp)
        #     if index + 2 < len(stoneValues):
        #         temp = stoneValues[index] + stoneValues[index+1] + stoneValues[index+2] - helper(stoneValues,index+3)
        #         ans = max(ans,temp)
        #     mem[index] = ans
        #     return ans
        # ans = helper(stoneValue,0)
        mem = {i:0 for i in range(len(stoneValue)+1)}
        i = len(stoneValue) - 1
        while i >= 0:
            ans = stoneValue[i] - mem[i+1]
            if i + 1 < len(stoneValue):
                ans = max(ans,stoneValue[i] + stoneValue[i+1] - mem[i+2])
            if i + 2 < len(stoneValue):
                 ans = max(ans,stoneValue[i] + stoneValue[i+1] + stoneValue[i+2] - mem[i+3])
            mem[i] = ans
            i -= 1
        if ans > 0:
            return 'Alice'
        elif ans < 0:
            return 'Bob'
        return 'Tie'

class Solution:
    def stoneGameIII(self, s: List[int]) -> str:
        cost = [0]*(len(s)+1)
        i = len(s)-1
        while i>=0:
            ans = -sys.maxsize
            ans = max(ans, s[i] - cost[i+1])
            if i+1 < len(s):
                ans = max(ans, s[i]+s[i+1] - cost[i+2])
            if i+2 < len(s):
                ans = max(ans, s[i]+s[i+1]+s[i+2] - cost[i+3])
            cost[i] = ans
            i -= 1
            
        a = cost[0]
        if a > 0:
            return 'Alice'
        if a == 0:
            return 'Tie'
        return 'Bob'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        # Get the highest socre of Alice s1, 
        # then score of Bob is sum(stoneValue) - s.
        # If s1 > s2 => Alice, if s1 == s2 => Tie, else
        # Bob
        
        # [1,2,3,6]
        # TLE, because in getScore we have to sum(stoneValue) since we 
        # don't need to get the explict score. Instead we only need to
        # consider the highest score that the first player win over the
        # other. Therefore, we can optimize it, which is the second 
        # approach. DP solution also uses this idea.
#         memo = {}
#         def getScore(start):
#             if start >= len(stoneValue):
#                 return 0
#             if start in memo:
#                 return memo[start]
#             res = -math.inf
#             front = 0
#             behind = sum(stoneValue[start:])
#             for i in range(start, min(start+3, len(stoneValue))):
#                 front += stoneValue[i]
#                 behind -= stoneValue[i]
#                 cur = front + behind - getScore(i+1)
#                 res = max(cur, res)
            
#             return res
                
#         s1 = getScore(0)
#         s2 = sum(stoneValue) - s1
        
#         if s1 > s2:
#             return 'Alice'
#         elif s1 == s2:
#             return 'Tie'
#         else:
#             return 'Bob'
        
#         # Second approach
#         memo = {}
#         def dfs(start):
#             if start >= len(stoneValue):
#                 return 0
#             if start in memo:
#                 return memo[start]
#             memo[start] = -math.inf
#             score = 0
#             for i in range(start, min(len(stoneValue), start+3)):
#                 score += stoneValue[i]
#                 memo[start] = max(memo[start], score - dfs(i+1))
            
#             return memo[start]
#         score = dfs(0)
        
#         if score > 0:
#             return 'Alice'
#         elif score == 0:
#             return 'Tie'
#         else:
#             return 'Bob'
            
        # DP solution
        n = len(stoneValue)
        dp = [-math.inf] * n
        for i in range(n-1, -1, -1):
            take = 0
            for j in range(i, min(i+3, n)):
                take += stoneValue[j]
                if j + 1 == n:
                    dp[i] = max(dp[i], take)
                else:
                    dp[i] = max(dp[i], take - dp[j+1])
        if dp[0] > 0:
            return 'Alice'
        elif dp[0] == 0:
            return 'Tie'
        else:
            return 'Bob'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        #--- corner case
        if not stoneValue:
            return 'Tie'
        
        #--- setup
        n = len(stoneValue)
        dp = [0 for _ in range(n+3)]
        stoneValue = stoneValue + [0,0,0]
        #--- main
        for i in range(n-1, -1, -1):
            max_v = float('-inf')
            curr = stoneValue[i]
            for j in range(i+1, i+4):
                max_v = max(max_v, curr - dp[j])
                curr += stoneValue[j]
            dp[i] = max_v
        # print(dp)
        if dp[0] > 0:
            return 'Alice'
        if dp[0] < 0:
            return 'Bob'
        return 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n: int = len(stoneValue)
        dp: List[int] = [0 for _ in range(n + 1)]
        for i in range(n - 1, -1, -1):
            dp[i] = float('-inf')
            taken: int = 0
            for j in range(3):
                if i + j < n:
                    taken += stoneValue[i + j]
                    dp[i] = max(dp[i], taken - dp[i + j + 1])
        if dp[0] > 0:
            return 'Alice'
        elif dp[0] < 0:
            return 'Bob'
        else:
            return 'Tie'

from functools import lru_cache
class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        @lru_cache(maxsize=None)
        def score(i):
            if i == N - 1: return stoneValue[i]
            if i == N - 2: 
                return max(stoneValue[i] + stoneValue[i+1],
                          stoneValue[i] - stoneValue[i+1],)
            if i == N - 3:
                return max(sum(stoneValue[i:]), stoneValue[i] - score(i+1),
                          sum(stoneValue[i:i+2]) - score(i+2))
            return max(stoneValue[i] - score(i+1),
                   sum(stoneValue[i:i+2]) - score(i+2),
                   sum(stoneValue[i:i+3]) - score(i+3))
        N = len(stoneValue)
        s = score(0)
        if s > 0: return 'Alice'
        elif s < 0: return 'Bob'
        else: return 'Tie'


class Solution:
  def stoneGameIII(self, stoneValue: List[int]) -> str:
    n = len(stoneValue)
    dp = [0] * (n + 3)

    total = 0
    for i in range(n - 1, -1, -1):
      total += stoneValue[i]
      dp[i] = -float('inf')
      for k in range(1, 4, 1):
        dp[i] = max(total - dp[i + k], dp[i])

    oppo = total - dp[0]
    if dp[0] > oppo:
      return 'Alice'
    elif dp[0] < oppo:
      return 'Bob'
    return 'Tie'


from functools import lru_cache
class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        @lru_cache
        def score(i):
            if i == N - 1: return stoneValue[i]
            if i == N - 2: 
                return max(stoneValue[i] + stoneValue[i+1],
                          stoneValue[i] - stoneValue[i+1],)
            if i == N - 3:
                return max(sum(stoneValue[i:]), stoneValue[i] - score(i+1),
                          sum(stoneValue[i:i+2]) - score(i+2))
            return max(stoneValue[i] - score(i+1),
                   sum(stoneValue[i:i+2]) - score(i+2),
                   sum(stoneValue[i:i+3]) - score(i+3))
        N = len(stoneValue)
        s = score(0)
        if s > 0: return 'Alice'
        elif s < 0: return 'Bob'
        else: return 'Tie'

from typing import List

class Solution:
    def stoneGameIII(self, stones: List[int]) -> str:
        suffix_sum = [0]
        for stone in stones[::-1]:
            suffix_sum += suffix_sum[-1] + stone,

        suffix_sum = suffix_sum[::-1][:-1]
        length = len(stones)
        dp = [float('-inf')] * (length - 3) + suffix_sum[-3:]
        for i in range(length - 2, -1, -1):
            dp[i] = max(dp[i], suffix_sum[i] - min(dp[i + j] for j in range(1, 4) if i + j < length))

        alice = dp[0]
        bob = suffix_sum[0] - dp[0]
        return 'Tie' if alice == bob else 'Alice' if alice > bob else 'Bob'

from functools import lru_cache
class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        # time complexity: O(n)
        # space complexity: O(n)
        @lru_cache(maxsize=None)
        def score(i):
            if i >= len(stoneValue): return 0
            #return max([sum(stoneValue[i:i+k]) - score(i+k) for k in [1,2,3]])
            return max([sum(stoneValue[i:i+1]) - score(i+1),
                        sum(stoneValue[i:i+2]) - score(i+2),
                        sum(stoneValue[i:i+3]) - score(i+3)])
        
        s = score(0)
        if s > 0: return 'Alice'
        elif s < 0: return 'Bob'
        else: return 'Tie'

from functools import lru_cache
class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        # time complexity: O(n)
        # space complexity: O(n)
        @lru_cache(maxsize=None)
        def score(i):
            if i >= len(stoneValue): return 0
            return max([sum(stoneValue[i:i+1]) - score(i+1),
                        sum(stoneValue[i:i+2]) - score(i+2),
                        sum(stoneValue[i:i+3]) - score(i+3)])
            #return max([sum(stoneValue[i:i+k]) - score(i+k) for k in [1,2,3]])
        
        s = score(0)
        if s > 0: return 'Alice'
        elif s < 0: return 'Bob'
        else: return 'Tie'

class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        n = len(stoneValue)
        p = [0] * n
        for i in range(n-1,-1,-1):
            if i == n-1: p[i] = stoneValue[i]
            else: p[i] = stoneValue[i] + p[i+1]

        dp = [0] * (n+1)
        for i in range(n-1,-1,-1):
            dp[i] = p[i] - min(dp[i+1:i+4])
        if dp[0] * 2 == p[0]: return 'Tie'
        elif dp[0] * 2 > p[0]: return 'Alice'
        else: return 'Bob'
                
            


class Solution:
    def stoneGameIII(self, stoneValue: List[int]) -> str:
        dp = [0]*3
        for i in range(len(stoneValue) - 1, -1, -1):
            dp[i % 3] = max(sum(stoneValue[i: i+k]) - dp[(i + k) % 3] for k in (1, 2, 3))
        if dp[0] == 0:
            return 'Tie'
        elif dp[0] < 0:
            return 'Bob'
        return 'Alice'