사과 게임

Alf와 Beata에게는 $N$그루의 사과나무가 길게 한 줄로 자라는 매우 긴 정원이 있다. 여름마다 나무에는 사과가 가득 열린다. 그러면 두 사람은 그 나무들로 게임을 한다. 게임에서 Alf와 Beata는 번갈아 가며, 어떤 $i$에 대해 가장 왼쪽 나무에서부터 $i$, $i + 2$, $i + 4$만큼 떨어진 위치에 있는, 사이에 정확히 나무 하나씩을 둔 세 나무의 사과를 모두 딴다. 이러한 수는 세 나무 중 어느 나무에서도 이전 수에 의해 사과를 딴 적이 없는 경우에만 유효하다. 자신의 차례에 유효한 수가 없는 플레이어가 패배한다. $N$이 주어질 때, Alf가 먼저 수를 둔다면 Alf와 Beata 중 누가 게임에서 이기는지 판별할 수 있는가?

채점

문제를 완전히 해결하면 $2$점을 받는다.

$1$점을 받으려면 $N \le 1\,000$인 경우에 대해서만 문제를 해결하면 된다.

입력은 사과나무의 수를 나타내는 하나의 정수 $N$ ($5 \le N \le 1\,000\,000$)으로 이루어진다.

Alf(먼저 수를 두는 플레이어)가 이기면 alf을 출력한다. 그렇지 않으면 beata을 출력한다.