Алиса и Боб играют в игру. У них есть $n$ кучек камней, в $i$-й кучке находится $a_i$ ($1 \le a_i \le n$) камней. В свой ход каждый игрок, начиная с Алисы, выбирает любую кучку и забирает из неё от одного до $x$ камней включительно. Игрок, который не может сделать ход (все кучки пусты), проигрывает. Алиса и Боб ещё не решили, чему будет равно конечное значение $x$, поэтому они попросили вас выяснить, кто победит при оптимальной игре обоих игроков для всех значений $x$, таких что $1 \le x \le n$.

Входные данные

Первая строка входных данных содержит одно целое число $n$ ($1 \le n \le 500\,000$): количество кучек и верхняя граница количества камней в кучках. Вторая строка содержит $n$ целых чисел $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$): количество камней в кучках.

Выходные данные

Выведите $n$ слов, где $i$-е из них — «Alice», если Алиса победит при оптимальной игре для $x = i$, и «Bob» в противном случае.

Примеры

Входные данные 1

6
6 6 6 6 6 6

Выходные данные 1

Bob Bob Bob Bob Bob Bob

Примечание

В первом примере, независимо от $x$, Боб может делать симметричные ходы (такой же ход в кучке с таким же количеством камней), поэтому на каждом ходу у него гарантированно будет хотя бы один доступный ход.

Входные данные 2

4
1 2 3 4

Выходные данные 2

Bob Alice Bob Alice

Входные данные 3

5
1 2 3 2 2

Выходные данные 3

Bob Alice Bob Bob Bob