Bessie ב־Camelot בצרה: לעבור יער Knights of Ni. דרשו שיח יחיד למעבר בטוח. הזמן דוחק, חייבת למצוא ולהביא מהר ככל האפשר.

מפה ברשת ריבועית רגילה מקבילה לצירי $X$, $Y$, גודל $W\times H$ ($1 \le W \le 1000$; $1 \le H \le 1000$).

מסומנים התחלה, המשבצת היחידה לאבירים, כל השיחים ואזורים עבירים. ביצות, צוקים וארנבים רצחניים חוסמים חלק. בלי שיח אסור לעבור במשבצת האבירים.

לפי המפה רק צפון מזרח דרום מערב, לא אלכסון. מעבר לשכנה אורך יום.

מציאה ומסירה מובטחות. מצאו דרך מהירה ביותר.

קלט

שורה $1$: שלמים $W$, $H$ ברווח.

שורות $2..?$: המפה שורה אחר שורה, ראשונה צפון־מערבית ואחרונה דרום־מזרחית, מספרים ממערב למזרח. שורת מפה חדשה מתחילה שורת קלט חדשה, לכל היותר 40 שלמים ברווחים. $W \le 40$ שורה שלמה בשורת קלט; $W > 40$ כמה שורות עם 40 בכל אחת פרט אולי לאחרונה. שורת קלט לא מכילה יותר משורת מפה אחת.

ערכים:

• 0: עביר.
• 1: חסום.
• 2: התחלת Bessie.
• 3: Knights of Ni.
• 4: שיח.

פלט

שורה $1$: $D$, מינימום ימים למציאת שיח ומסירתו.

דוגמאות

קלט 1

8 4
4 1 0 0 0 0 1 0
0 0 0 1 0 1 0 0
0 2 1 1 3 0 4 0
0 0 0 4 1 1 1 0

פלט 1

11

הערה

רוחב $8$, גובה $4$, מתחילה שורה שלישית קרוב לאבירים.

אפשר N, W, N, S, E, E, N, E, E, S, S: השיח בצפון־מערב, עוקפת מחסומים מזרחה ואז דרומה לאבירים.