토너먼트가 주어지며, 이는 완전 방향성 그래프(서로 다른 두 정점의 모든 쌍 $i, j$에 대해 $i \to j$와 $j \to i$ 중 정확히 하나의 간선이 존재함)로 표현되고 정점의 개수는 $n \le 3000$입니다. 이 그래프의 간선들을 14가지 색으로 칠해야 합니다.

그래프에서 간선 $i \to j$와 $j \to k$의 색이 같은 경로 $i \to 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$와 $j \to k$의 색이 같은 경로 $i \to j \to k$가 존재해서는 안 됩니다.

예제

입력 1

3
1
11

출력 1

a
ab

입력 2

5
1
10
100
0100

출력 2

a
bc
def
ghij