یک جدول $n\times n$ داریم که خانه‌ی ردیف $i$ام و ستون $j$ ام آن را با $(i,j)$ نشان می‌دهیم. یک ملخ داریم که از خانه‌ی $(a,b)$ شروع می‌کند و می‌خواهد به خانه‌ی $(c,d)$ برسد. اما عبور از برخی از خانه‌های جدول غیر مجاز می‌باشد. حرکت ملخ بدین صورت است که در هر حرکت، می‌تواند به اولین خانه‌ی مجاز چپ٬ راست، بالا و پایین خود (در صورت وجود) بپرد. هدف این است که ملخ با کم‌ترین تعداد چرخش(تغییر جهت) به هدف برسد. فرض کنید که خانه‌های مبدا و مقصد مجاز هستند.

در سطر اول فایل ورودی اعداد $c،b،a،n$ و $d$ به ترتیب آمده‌اند. سپس در $n$ سطر بعد، در هر سطر $n$ عدد آمده است که عدد $j$ام سطر $i$ام این $n$ سطر، اگر $(i,j)$ مجاز باشد ۱ است و در غیر این صورت ۰ می‌باشد.$(n \leq 1000)$

در سطر اول فایل خروجی تعداد خانه‌ها در مسیر بهینه را بنویسید(خانه‌های مبدا و مقصد جز مسیر محسوب می‌شوند.) سپس در سطر‌های بعد،در هر سطر شماره‌ ردیف و ستون یک خانه از مسیر را بنویسید (که بالطبع باید خانه‌های متوالی در مسیر از مبدا به مقصد باشند).

در صورتی که مسئله جواب نداشته باشد٬ در یک سطر بنویسید $No Solution$.

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل