Vous disposez d'un tournoi, représenté par un graphe orienté complet (pour toutes les paires $i, j$ de deux sommets distincts, il existe exactement une arête parmi $i \to j$ et $j \to i$), avec $n \le 3000$ sommets. Vous devez colorier ses arêtes avec 14 couleurs.

Il ne doit pas y avoir de chemin $i \to j \to k$ dans ce graphe tel que les couleurs des arêtes $i \to j$ et $j \to k$ soient identiques.

Il est garanti que cela est toujours possible.

Entrée

La première ligne de l'entrée contient un entier $n$ ($3 \le n \le 3000$) : le nombre de sommets dans le tournoi donné.

Les $n - 1$ lignes suivantes contiennent la description du graphe : la $i$-ième ligne contient une chaîne binaire de $i$ caractères.

Si le $j$-ième caractère de cette chaîne est égal à '1', alors le graphe possède une arête de $(i+1) \to j$. Sinon, il possède une arête de $j \to (i+1)$.

Sortie

La sortie doit contenir $n - 1$ lignes, où la $i$-ième ligne contient une chaîne de $i$ caractères.

Le $j$-ième caractère de cette chaîne doit être une lettre latine minuscule comprise entre 'a' et 'n'. Si le graphe possède une arête de $(i+1) \to j$, alors ce caractère représente la couleur de l'arête de $(i+1) \to j$. Sinon, il représente la couleur de l'arête de $j \to (i+1)$.

Il ne doit pas y avoir de chemin $i \to j \to k$ dans ce graphe tel que les couleurs des arêtes $i \to j$ et $j \to k$ soient identiques.

Exemples

Entrée 1

3
1
11

Sortie 1

a
ab

Entrée 2

5
1
10
100
0100

Sortie 2

a
bc
def
ghij