Problem E
The Apple Game
Alf and Beata have a very long garden in which $N$ apple trees grow in a long line. Each summer, the trees become filled with apples. They then play a game with the trees. In the game, Alf and Beata take turns picking all the apples from three trees which are separated by exactly one tree, i.e. from the trees $i$, $i + 2$ and $i + 4$ spots from the leftmost tree for some $i$. Such a move is only valid if none of the three trees had their apples picked from them in a previous move. A player without a valid move on their turn loses. Given $N$, can you determine if Alf or Beata wins the game if Alf moves first?
Input
The input consists of a single integer $N$ ($5 \le N \le 1\, 000\, 000$), the number of apple trees.
Output
If Alf (the first player) wins, output alf. Otherwise, output beata.
Scoring
If you solve the problem fully, you get $2$ points.
To get $1$ point, you only need to solve the problem for cases where $N \le 1\, 000$.
| Sample Input 1 | Sample Output 1 |
|---|---|
5 |
alf |
| Sample Input 2 | Sample Output 2 |
|---|---|
6 |
beata |
| Sample Input 3 | Sample Output 3 |
|---|---|
7 |
beata |
