Alice and Bob are playing a game with a string of English alphabets (both uppercase and lowercase). They can select a character either from the start or end of the string. Put the selected character in a common box. The winner of the game is the first person who can make a string palindrome of length greater than 1 by using some of the box's characters. Alice starts first to pick a character and both players play optimally. Determine the winner of the game or depict if it is a Tie.
Note: A tie occurs when no one wins.
For example: If the string is aabc, then Alice can select the character 'a' or 'c' and store it into the box. If Alice chooses 'a', then the resulting string for Bob is abc. This helps Bob so that he can select either 'a' or 'c', so he can select 'a' and store it into box. Now, Bob can make a string 'aa' which is a palindrome of length is greater than 1. Hence, Bob wins the game.
Input format
The only line contains a string s of n lowercase and uppercase English letters. (1≤|s|≤105)
Output format
If Alice wins the game, then print Alice. If Bob wins the game, then print Bob. If no one wins the game, then print Tie.
In abcabc, we can see that if Alice picks 'a' and store in a box then Bob can pick 'c' or 'b', if Bob picks 'b' and store it into box then Alice can pick either 'c' from starting and store in the box, Now Bob can pick 'a' or 'c', But we can see that if he picks 'a' and store in the box. Then using box characters a palindrome of length > 1 can be formed "aa" hence Bob is the winner.
