You are given a tournament, represented as a complete directed graph (for all pairs $i,j$ of two different vertices, there is exactly one edge among $i\to j$ and $j\to i$), with $n\le3000$ vertices. You need to color its edges into 14 colors.

There should be no path $i\to j\to k$ in this graph such that the colors of edges $i\to j$ and $j\to k$ are the same.

It is guaranteed that this is always possible.

Input

The first line of input contains one integer $n$ ($3\le n\le3000$): the number of vertices in the given tournament.

Next $n-1$ lines contain the description of the graph: the $i$-th line contains a binary string with $i$ characters.

If the $j$-th character in this string is equal to 1, then the graph has an edge from $(i+1)\to j$. Otherwise, it has an edge from $j\to(i+1)$.

Output

The output should contain $n-1$ lines, where the $i$-th line contains a string with $i$ characters.

The $j$-th character in this string should be a lowercase Latin letter between a and n. If the graph has an edge from $(i+1)\to j$, then this character represents the color of the edge from $(i+1)\to j$. Otherwise it represents the color of the edge from $j\to(i+1)$.

There should be no path $i\to j\to k$ in this graph such that the colors of edges $i\to j$ and $j\to k$ are the same.

Examples

Input 1

3
1
11

Output 1

a
ab

Input 2

5
1
10
100
0100

Output 2

a
bc
def
ghij