נתון טורניר, המיוצג כגרף מכוון מלא (לכל זוג קודקודים שונים $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