Вам дан турнир, представленный в виде полного ориентированного графа (для любой пары различных вершин $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