Hacky has been depressed lately given that his Cat has been defeating in every game they've been playing. But Hacky has not yet given up hope ... he has designed another new game to try and beat his Cat:
- Hacky and the Cat alternate playing first in each game.
- A list of random numbers (of random length) is generated using a program that Hacky wrote and the Cat verified (see note below).
- In each turn, the player can either choose to eliminate all odd-indexed numbers or all even indexed numbers.
- The final number is the outcome of the game. If this final value is less than the average of all the numbers in the list, the player who played first loses, else he/she/it wins.
Assuming both players play optimally, you have to determine who will win the game.
Note: Hacky's Cat knows more than a 100 programming languages, is an expert in Software Development, and has a rating so high on TopCoder that the website crashed (back in 2004) due to a long long integer overflow. It has rejected job offers from Facebook, Google & Quora, as it prefers doing far more satisfying things like sleeping, drinking milk, hunting mice, and flirting with female cats from Hostels 8 and 9.
- Each line will consist of the name of the player (either "Hacky" or "Cat") who will play first, followed by the non-empty list of random numbers.
- Corresponding to each line of the input, you need to output the name of the winner (either "Hacky" or "Cat").
- The length of the list will be less than 10000, and each element in the list will be less than 10000 too.
Hacky 1 2 3 4
Cat 6 3 8 1 2 4 7 5
Hacky 9 3 1 6 4 2 8 7 3
Problem Setter: Kaustubh Karkare