یک جدول مستطیلی $m\times n$‌ از اعداد طبیعی داریم. می‌خواهیم یک تاس را از نقطه‌ی $(a,b)$ جدول، روی اضلاع خانه‌های جدول بغلتانیم و به نقطه $(c,d)$ برسیم. تاس در هر خانه‌ای که قرار بگیرد اگر عدد کف تاس (عددی که روی وجه پایین آن نوشته شده) $x$ و عدد خانه‌ی مورد نظر $y$ باشد جریمه‌ای برابر $(x-y)^2$ به ما تعلق می‌گیرد. می‌خواهیم طوری حرکت کنیم که کم‌ترین جریمه را بپردازیم. (هنگامی که در خانه $(a,b)$ هستیم و همچنین وقتی به خانه‌ی $(c,d)$ می‌رسیم نیز باید جریمه بپردازیم.)

$(1,1)$ خانه‌ی بالا چپ و $(m,n)$ خانه‌ي پایین و راست جدول است. خانه‌ی $(x,y)$ یعنی خانه‌ای که در سطر $x$ ام و ستون $y$ ام قرار دارد.

تاس را طوری می‌توان قرار داد که وجه کف آن ۱، وجه راست آن ۲، وجه جلوی آن ۳، وجه پشت آن ۴، وجه چپ آن ۵ و وجه روی آن ۶ باشد.

در خط اول فایل ورودی اعداد $m$ و $n$ ($1 \leq m,n \leq 20$) و در خط دوم $a$ و $b$ و $c$ و $d$ و در خط سوم عدد کف تاس و عدد روی وجه جلوی تاس در زمان شروع حرکت داده شده است. در $m$ خط بعد در هر خط $n$ ‌ عدد داده شده است که سطر $i+3$ ام ورودی، سطر $i$ ام جدول است.

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

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

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