Дано турнір, поданий як повний орієнтований граф (для кожної пари різних вершин $i,j$ існує рівно одне з ребер $i \to j$ та $j \to i$), із $n \le 3000$ вершинами. Потрібно розфарбувати його ребра у $14$ кольорів.

У цьому графі не повинно бути шляху $i \to j \to k$, на якому ребра $i \to j$ та $j \to k$ мають однаковий колір.

Гарантується, що це завжди можливо.

Вхідні дані

Перший рядок вхідних даних містить одне ціле число $n$ ($3 \le n \le 3000$) — кількість вершин заданого турніру.

Наступні $n-1$ рядків містять опис графа: $i$-й рядок містить двійковий рядок із $i$ символів.

Якщо $j$-й символ цього рядка дорівнює 1, то у графі є ребро $(i+1) \to j$. Інакше є ребро $j \to (i+1)$.

Вихідні дані

Вивід має містити $n-1$ рядків, причому $i$-й рядок має містити рядок із $i$ символів.

$j$-й символ цього рядка має бути малою латинською літерою від a до n. Якщо у графі є ребро $(i+1) \to j$, то цей символ позначає колір ребра $(i+1) \to j$. Інакше він позначає колір ребра $j \to (i+1)$.

У цьому графі не повинно бути шляху $i \to j \to k$, на якому ребра $i \to j$ та $j \to k$ мають однаковий колір.

Приклади

Вхідні дані 1

3
1
11

Вихідні дані 1

a
ab

Вхідні дані 2

5
1
10
100
0100

Вихідні дані 2

a
bc
def
ghij