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: شجيرة شمال غرب ثم التفاف شرقًا حول الحواجز ثم جنوبًا للفرسان.