ماز

یک ماز یک جدول با $n$ سطر و $m$ ستون است که هر مربع واحد یک خانه‌ی ماز است. بین هر دو خانه می‌تواند یک دیوار وجود داشته باشد. دیوارهای ماز طوری چیده شده‌اند که بین هر دو خانه‌ی ماز دقیقاً یک مسیر وجود دارد. یک ماز بسته مازی است که هیچ ورودی و خروجی‌ای ندارد.

ارشیا یک ماز سه بعدی دارد. ماز سه بعدی به شکل یک مکعب مستطیل با ارتفاع $h$ و سطح مقطع $n$ در $m$ است. هر مکعب واحد از ماز یک خانه ماز نامیده می‌شود. صفحه بین هر دو خانه می‌تواند مسدود باشد. دیوارهای بین خانه‌ها طوری قرار دارند که بین هر دو خانه دقیقاً یک مسیر وجود دارد.

مکعب ارشیا پر از آب است. یعنی تمام خانه‌های ماز پر از آب هستند. ارشیا می‌خواهد آب درون مکعبش را خالی کند. او نمی‌تواند مکعب را جا به جا کند یا بچرخاند.

ارشیا باید بعضی از دیواره‌های بین دو خانه‌ی مجاور در ماز یا بین یک خانه و بیرون ماز را باز کند تا آب درون ماز بتواند از آن خارج شود. ارشیا زمانی راضی می‌شود که هیچ خانه‌ی جدول پر از آب نباشد.

در هر یک از جدول‌های زیر یک نمونه دو بعدی نمایش داده شده‌است. در هر نمونه یک دیوار عمودی و یک دیوار افقی حذف شده که با نقطه‌چین نشان داده شده‌اند. خانه‌های رنگی نشان‌دهنده‌ی خانه‌هایی هستند که پر از آب باقی می‌مانند.

دقت کنید که در دنیای واقعی ممکن است مقداری آب در خانه‌های سفید باقی بماند، اما ارشیا فقط به خانه‌های پر از آب اهمیت می‌دهد.

ارشیا می‌خواهد با حذف کمترین تعداد دیواره به هدفش برسد. او برای محاسبه این مقدار به کمک شما نیاز دارد.

قاعده‌ی مکعب مستطیل موازی سطح زمین قرار دارد. و اضلاع قاعده موازی محورهای مختصات هستند. هر یک از خانه‌های مکعب مستطیل را با یک سه‌تایی مرتب $(x,y,z)$ توصیف می‌کنیم.

$$0\leq x<n,\quad 0\leq y<m,\quad 0\leq z<h$$

جهت مثبت $x$ به سمت جنوب، جهت مثبت $y$ به سمت شرق و جهت مثبت $z$ به سمت پایین است.

در تصویر زیر مثالی از نحوه‌ی مختصات‌دهی برای یک صفحه با مؤلفه‌های $z$ برابر داده شده‌است.

ارشیا در ابتدا مختصات همه خانه‌ها را می‌نویسد. سپس این مختصات‌ها را به ترتیب کتابخانه‌ای¹⁾ مرتب می‌کند. به عنوان مثال برای $n,m,h=2$ ترتیب کتابخانه‌ای

$$\langle(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)\rangle$$

است.

سپس ارشیا در خط $i$-ام از $n\times m\times h$ خط ورودی، دیواره‌های دور خانه‌ی $i$-ام از ترتیب را توصیف می‌کند.

توصیف دیواره‌های دور هر خانه یک رشته به طول ۶ از ۰ و ۱ است.

1. بیت اول ۱ است اگر و تنها اگر دیواره‌ی بالای خانه مسدود باشد.
2. بیت دوم ۱ است اگر و تنها اگر دیواره‌ی پایین خانه مسدود باشد.
3. بیت سوم ۱ است اگر و تنها اگر دیواره‌ی شرقی خانه مسدود باشد.
4. بیت چهارم ۱ است اگر و تنها اگر دیواره‌ی غربی خانه مسدود باشد.
5. بیت پنجم ۱ است اگر و تنها اگر دیواره‌ی شمالی خانه مسدود باشد.
6. بیت ششم ۱ است اگر و تنها اگر دیواره‌ی جنوبی خانه مسدود باشد.

ورودی

در خط اول ورودی سه عدد $n$ و $m$ و $h$ آمده‌اند. در $n\times m\times h$ خط بعدی توصیفات ارشیا آمده است.

سه فایل با نام‌های maze-1.in، maze-2.in و maze-3.in در اختیار شما قرار داده شده‌اند که هر یک شامل ورودی برای یک ماز است.

تمام پاسخ‌های ارائه شده در این سوال با فرض $\Delta = 10256483$ محاسبه شده‌اند.

$1$- الف ($30$ نمره) : جواب مسئله را برای نمایش دو بعدی زیر از ماز توصیف شده در فایل maze-1.in را پیدا کنید. در این ماز داریم $m=1$.

در این تصویر سمت راست جهت جنوب و سمت بالا جهت بالای ماز است. اعداد نوشته شده درون ماز برای درک بهتر از ترتیب خانه‌ها در فایل ورودی است و تاثیری در مسئله ندارد.

اگر جواب $x$ باشد، $x^{42}$ را به پیمانه‌ی $\Delta$ چاپ کنید.

$1$- ب ($30$ نمره) : جواب مسئله برای ماز درون فایل maze-2.in را پیدا کنید. در این ماز داریم $m=1$.

اگر جواب $x$ باشد، $x^{42}$ را به پیمانه‌ی $\Delta$ چاپ کنید.

$1$- ج ($40$ نمره) : جواب مسئله برای ماز درون فایل maze-3.in را پیدا کنید.

اگر جواب $x$ باشد، $x^{42}$ را به پیمانه‌ی $\Delta$ چاپ کنید.