Alice et Bob jouent à un jeu.

Ils disposent de $n$ tas de pierres, tels qu'il y a $a_i$ ($1 \le a_i \le n$) pierres dans le $i$-ème tas.

À chaque tour, chaque joueur, en commençant par Alice, choisit un tas quelconque et en retire au moins une et au plus $x$ pierres.

Le joueur qui ne peut pas effectuer de mouvement à son tour (tous les tas sont vides) perd.

Alice et Bob n'ont pas encore décidé de la valeur finale de $x$, ils vous ont donc demandé de déterminer qui gagnera si les deux joueurs jouent de manière optimale pour toutes les valeurs de $x$, telles que $1 \le x \le n$.

Entrée

La première ligne de l'entrée contient un entier $n$ ($1 \le n \le 500\,000$) : le nombre de tas et la borne supérieure du nombre de pierres dans les tas.

La ligne suivante contient $n$ entiers, $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) : le nombre de pierres dans les tas.

Sortie

Affichez $n$ mots, où le $i$-ème d'entre eux est « Alice » si Alice gagne en jouant de manière optimale pour $i = x$, et « Bob » sinon.

Exemples

Entrée 1

6
6 6 6 6 6 6

Sortie 1

Bob Bob Bob Bob Bob Bob

Entrée 2

4
1 2 3 4

Sortie 2

Bob Alice Bob Alice

Entrée 3

5
1 2 3 2 2

Sortie 3

Bob Alice Bob Bob Bob

Remarque

Dans le premier exemple, indépendamment de $x$, Bob peut effectuer des mouvements symétriques (le même mouvement sur le tas ayant le même nombre de pierres), donc à chaque tour, il aura certainement au moins un mouvement disponible.