Bessie שוב תקועה בצד הלא נכון של האסם של Farmer John. ראייתה חלשה וזקוקה לעזרתכם לחצות אותו.

האסם הוא רשת $N \times N$ של תאים ריבועיים ($2 \leq N \leq 20$), ריקים או עם חציר בלתי עביר. מתחילה בשמאל התחתון $(1,1)$ ומבקשת ימין עליון $N,N$. הוראות: ״קדימה״, ״90 מעלות שמאלה״, ״90 מעלות ימינה״. דרוש רצף קצר ביותר. ביציאה מהרשת, לקיר, או לחציר לא תזוז ותעבור להוראה הבאה.

אינה יודעת אם מתחילה כלפי מעלה $(1,2)$ או ימינה $(2,1)$. תנו רצף קצר ביותר שיצליח בשניהם. בהגעה תתעלם מההמשך.

קלט

קראו מהקלט הסטנדרטי.

השורה הראשונה מכילה $N$.

$N$ הבאות מכילות בדיוק $N$ תווים. הראשון באחרונה $(1,1)$, האחרון בראשונה $(N,N)$.

H מציין חציר, E תא ריק.

$(1,1)$ ו־$N,N$ ריקים ומובטח מסלול ריק מ־$(1,1)$ ל־$N, N$.

פלט

כתבו לפלט הסטנדרטי.

הדפיסו שורה עם אורך הרצף הקצר ביותר המגיע ליעד בשני הכיוונים ההתחלתיים.

דוגמאות

קלט 1

3
EHE
EEE
EEE

פלט 1

9

הערה

״קדימה, ימינה, קדימה, קדימה, שמאלה, קדימה, שמאלה, קדימה, קדימה״ מצליח בשני כיווני הדוגמה.

מחבר הבעיה: Brian Dean