1248. Stone Game III

Stones with values (possibly negative) are in a row. Alice and Bob alternate turns, starting with Alice, and each turn a player takes 1, 2, or 3 stones from the front. The player with the larger total wins. Assuming optimal play, return 'Alice', 'Bob', or 'Tie'. The input is JSON {values}.

Input: JSON {values}.

Output: String — 'Alice', 'Bob', or 'Tie'.

Examples

Input: {"values":[1,2,3,7]}
Output: Bob
Explanation: Bob wins with optimal play.

Input: {"values":[1,2,3,-9]}
Output: Alice
Explanation: Alice wins.

Input: {"values":[1,2,3,6]}
Output: Tie
Explanation: Scores are equal.

Constraints

• 1<=n<=5*10^4

Asked by