תיאור

יהי $n \ge 1$. נתבונן בדרך הסטנדרטית הבאה לחלק משולש גדול ל-$n^2$ משולשים קטנים יותר על ידי סרטוט שלוש קבוצות של ישרים מקבילים זה לזה:

באופן טבעי, דבר זה מגדיר גרף לא מכוון עם $(n + 1)(n + 2)/2$ צמתים ו-$3n(n + 1)/2$ קשתות: הצמתים הם צומתי הרשת, או במילים אחרות נקודות החיתוך של הישרים (מסומנות בהדגשה באיור), והקשתות הן הקטעים שבין צמתים שכנים. משימתך היא לבנות מעגל אוילר על קשתות הגרף הזה אשר "מתחיל" מהצומת העליון ביותר של המשולש. במילים אחרות, עליך להתחיל בצומת העליון ביותר, לנוע לאורך הקשתות, לעבור בכל קשת בדיוק פעם אחת, ובסופו של דבר לחזור לצומת העליון ביותר. ניתן להוכיח שפתרון תמיד קיים.

קלט

נתון מספר שלם $n$ בטווח שבין $1$ ל-$20$.

פלט

הדפס מחרוזת של בדיוק $3n(n + 1)/2$ ספרות מ-$0$ עד $5$, המייצגת מעגל אוילר כלשהו של הגרף בפורמט הבא: $0$ משמעותו תנועה ישירות ימינה מהצומת הנוכחי, $1$ משמעותו תנועה בכיוון ימינה-למעלה, $2$ משמעותו תנועה שמאלה-למעלה, $3$ משמעותו תנועה שמאלה, $4$ משמעותו תנועה שמאלה-למטה, ו-$5$ משמעותו תנועה ימינה-למטה. לשם הבהירות, הכיוונים מוצגים באיור שלהלן.

המעבר חייב להתחיל מהצומת העליון. כל אחד מהמעברים האפשריים יתקבל.

דוגמה

2

404240022

הערה