Bạn được cho một giải đấu (tournament), được biểu diễn dưới dạng một đồ thị có hướng đầy đủ (với mọi cặp đỉnh $i, j$ phân biệt, luôn tồn tại chính xác một cạnh giữa $i \to j$ và $j \to i$), với $n \le 3000$ đỉnh. Bạn cần tô màu các cạnh của đồ thị bằng 14 màu.

Không được tồn tại đường đi $i \to j \to k$ nào trong đồ thị này sao cho màu của cạnh $i \to j$ và $j \to k$ giống nhau.

Đảm bảo rằng điều này luôn có thể thực hiện được.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên $n$ ($3 \le n \le 3000$): số lượng đỉnh trong giải đấu đã cho.

$n - 1$ dòng tiếp theo chứa mô tả của đồ thị: dòng thứ $i$ chứa một xâu nhị phân có độ dài $i$.

Nếu ký tự thứ $j$ trong xâu này bằng '1', thì đồ thị có một cạnh từ $(i+1) \to j$. Ngược lại, đồ thị có một cạnh từ $j \to (i+1)$.

Dữ liệu ra

Dữ liệu ra nên chứa $n - 1$ dòng, trong đó dòng thứ $i$ chứa một xâu có độ dài $i$.

Ký tự thứ $j$ trong xâu này phải là một chữ cái Latin thường từ 'a' đến 'n'. Nếu đồ thị có một cạnh từ $(i+1) \to j$, thì ký tự này đại diện cho màu của cạnh $(i+1) \to j$. Ngược lại, nó đại diện cho màu của cạnh $j \to (i+1)$.

Không được tồn tại đường đi $i \to j \to k$ nào trong đồ thị này sao cho màu của cạnh $i \to j$ và $j \to k$ giống nhau.

Ví dụ

Dữ liệu vào 1

3
1
11

Dữ liệu ra 1

a
ab

Dữ liệu vào 2

5
1
10
100
0100

Dữ liệu ra 2

a
bc
def
ghij