Alice and Bob are playing a game. At first, there are positive integers written on the blackboard. They then take turns making a move, with Alice going first, which consists of the following: choose any integer on the blackboard, erase , and write positive integers and on the blackboard, such that and . The first player who is unable to make a move loses. Find who wins the game if both players play optimally.
Subtask 1 [10%]
is a power of .
Subtask 2 [90%]
No additional constraints.
The first line contains the integer .
The next line contains space-separated integers, representing the list of positive integers initally written on the blackboard.
ALICE if Alice wins, otherwise output
3 36 72 108