صالح در راه بازگشت از خونه با باشگاه با موجودی افسانه‌ای به نام «اژدمارنگ‌کول» مواجه شد. اژدمارنگ می‌خواست که نذاره صالح به باشگاه برسه؛ به صالح پیش‌نهاد یک بازی را کرد. صفحه‌ای جادویی به شکل صفحه‌ی شطرنج اما با ترکیب رنگی متفاوت را پیش روی صالح قرار داد. هر خانه‌ی جدول یک رنگی دارد. هرگاه که بازیکن درخواست کند، در یکی از خانه‌های این صفحه که به خانه‌ی «اژدر» معروف است، یک تاس «کول» ظاهر می‌شود. شکل و شمایل این تاس‌ها یکسان می‌باشد. یعنی رنگ وجوه متناظر کول‌های ظاهر شده یکسان است.

در یک حرکت می‌توان یک تاس را از محل کنونی به یکی از خانه‌های مجاور غلطاند. اگر یک تاس در خانه‌ای قرار بگیرد که رنگ آن خانه با رنگ وجه زیرین تاس متفاوت باشد، آن تاس منفجر می‌شود. در ضمن از آن‌جایی‌که این تاس‌ها غیر مادی هستند، ممکن است در یک لحظه دو تاس در یک خانه قرار بگیرد.

بعضی از خانه‌های صفحه علامت‌گذاری شده‌اند و به آن‌ها خانه‌های «مانگ» می‌گوییم. در انتها بایستی در خانه‌های مانگ تاس وجود داشته باشد.

درخواست اژدرمانگ از صالح رساندن تاس به تمام خانه‌های مانگ با کم‌ترین تعداد حرکت می‌باشد. به وی در این امر خطیر کمک رسانید. ساختار صفحه، محل خانه‌ی اژدر، محل خانه‌های مانگ و شکل تاس کول ظاهر شده به شما داده می‌شود.

در سطر اول فایل ورودی، $n$ تعدد خانه‌های واقعی صفحه و مختصات خانه‌ی اژدر آمده است.

در $n$ سطر بعدی توضیح خانه‌های صفحه آمده است: ابتدا مختصات و سپس رنگ خانه که یک رشته‌ي حداکثر ۱۰ حرفی است. در انتها نیز ۰ به معنی مانگ نبودن و ۱ به معنی مانگ بودن خانه‌ی مورد بحث است.

سپس توصیف تاس کول آمده: به ترتیب رنگ خانه‌ی زیرین، فوقانی، شمالی (در جهت مثبت $y$)، شرقی (در جهت مثبت $x$)، جنوبی و غربی آمده است.

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

توجه

می‌دانیم که $1\leq n \leq 10^5$ و هر مختصه‌ی یک خانه در بازه‌ی $[0...10^4]$ قرار دارد.

رنگ وجوه مختلف تاس کول متفاوت است. در انتها اگر دو خانه‌ی مانگ مجاور هستند، رنگ وجوه مجاور تاس‌های حاضر در آن‌ها نیز بایستی یکسان باشد. وجوه مجاور یعنی وجوهی که یکدیگر را لمس می‌کنند.

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