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: MEDIUM
Tags: Dynamic programming

Data structures

Game theory

Mathematics
Skill types: Dynamic programming

Data structures

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, 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
		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, 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])
		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:
		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:
		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 = [-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])
		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:

	def bottomUpDP(self, stoneValue: List[int]) -> str:
		n = len(stoneValue)
		suffix_sum = [0 for _ in range(n + 1)]
		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]:
			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:
		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:
		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)
		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:

	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:
		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):
				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)
		if ans > 0:
			return 'Alice'
		elif ans < 0:
			return 'Bob'
		else:
			return 'Tie'


class Solution:

	def stoneGameIII(self, stoneValue: List[int]) -> str:
		n = len(stoneValue)
		cache = dict()

		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) = (-1000000000.0, -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]
		if p1 > p2:
			return 'Alice'
		elif p1 == p2:
			return 'Tie'
		return 'Bob'


class Solution:

	def stoneGameIII(self, stones):
		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):
		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):
		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'

class Solution1:

	def stoneGameIII(self, stoneValue: List[int]) -> str:
		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:
					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 stoneGameIII2(self, stoneValue: List[int]) -> str:
		n = len(stoneValue)
		cache = dict()

		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:
		(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:
		(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:
		length = len(stoneValue)
		dp = {}
		kA = 'Alice'
		kB = 'Bob'
		for index in range(length - 1, -1, -1):
			minus = length - index
			rA = rB = 0
			if minus >= 3:
				c1 = stoneValue[index] + stoneValue[index + 1] + stoneValue[index + 2]
				c2 = stoneValue[index] + stoneValue[index + 1]
				c3 = stoneValue[index]
				rA = max(c1 + dp.get((index + 3, kB), 0), c2 + dp.get((index + 2, kB), 0), c3 + dp.get((index + 1, kB), 0))
				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:
				c1 = stoneValue[index] + stoneValue[index + 1]
				c2 = stoneValue[index]
				rA = max(c1, c2 + dp.get((index + 1, kB), 0))
				rB = min(-c1, -c2 + dp.get((index + 1, kA), 0))
			elif minus == 1:
				c1 = stoneValue[index]
				rA = c1
				rB = -c1
			dp[index, kA] = rA
			dp[index, kB] = rB
		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)
		dp[n] = 0
		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
		s = stoneValue
		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'


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]
		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'


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, stones: List[int]) -> str:
		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: 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:
		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):
		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))
		self.cache[i] = res
		return res


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):
			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))
			best[index] = res
			return best[index]
		res = findbest(0, stoneValue)
		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)
			(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]
		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'


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):
			if i >= len(A):
				return 0
			if i == len(A) - 1:
				return A[-1]
			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:
		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))
			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)))
			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)))
			memo[i] = maxi
			return maxi
		aliceScore = dfs(stoneValue, 0, memo)
		bobScore = sum(stoneValue) - aliceScore
		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)
		if a > b:
			return 'Alice'
		elif a < b:
			return 'Bob'
		else:
			return 'Tie'


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:
			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])
		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:

		@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'


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'


class Solution:

	def stoneGameIII(self, stoneValue: List[int]) -> str:
		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
		return 'Alice' if first > second else 'Tie' if first == second else 'Bob'

	def stoneGameIII(self, stoneValue: List[int]) -> str:
		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'


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:
		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'


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)
		winner = 'Alice' if dp[0] > 0 else 'Bob' if dp[0] < 0 else 'Tie'
		return winner


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):
			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
		initIndex = 0
		stoneValueLength = len(stoneValue)
		mem = {}
		if stoneValueLength == 0:
			return 'Tie'
		else:
			result = self.recursiveHelper(stoneValue, stoneValueLength, initIndex, firstSelect, mem)
			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:
			curr = stoneValue[index]
			c1 = curr if flag else -curr
			mem[index, flag] = c1
			return c1
		elif minus == 2:
			curr = stoneValue[index] + stoneValue[index + 1]
			c1 = curr if flag else -curr
			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:
			curr = stoneValue[index] + stoneValue[index + 1] + stoneValue[index + 2]
			c1 = (curr if flag else -curr) + self.recursiveHelper(stoneValue, length, index + 3, not flag, mem)
			curr = stoneValue[index] + stoneValue[index + 1]
			c2 = (curr if flag else -curr) + self.recursiveHelper(stoneValue, length, index + 2, not flag, mem)
			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:
		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'


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':
				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.0:
			return 'Alice'
		elif alex_score < total_value / 2.0:
			return 'Bob'
		else:
			return 'Tie'


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):
					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)
				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
		if aScore == bScore:
			return 'Tie'
		elif aScore > bScore:
			return 'Alice'
		else:
			return 'Bob'


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:
			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]
			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]
			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:
			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]
			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]
			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, 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'


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:
		(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'


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
		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:
		if not stoneValue:
			return 'Tie'
		n = len(stoneValue)
		dp = [0 for _ in range(n + 3)]
		stoneValue = stoneValue + [0, 0, 0]
		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
		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'


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'


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'