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

چرخ بازی همان طور که از اسمش پیداست یک بازی است که با تعدادی چرخ انجام می‌شود. اعداد صفر تا ۹ پشت سر هم و ساعت گرد روی محیط هر چرخ نوشته شده‌اند. رقم‌های بالایی چرخ‌ها تشکیل یک عدد صحیح می‌دهند. به عنوان مثال وضعیت چرخ ها در شکل زیر عدد ۰۱۳۹۴ را نشان می‌دهد. در زیر هر چرخ دو کلید وجود دارد. کلید سمت چپ چرخ را به اندازه‌ی یک رقم در جهت ساعت گرد می‌چرخاند. کلید سمت راست آن را به اندازه یک رقم در جهت مخالف می‌چرخاند.

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

ورودی

خط اول ورودی شامل ۵ رقم است که وضعیت اولیه‌ی چرخ‌ها را نشان می‌دهند. در خط بعدی نیز ۵ رقم می‌آیند که نشان‌دهنده‌ی وضعیت نهایی هستند. در خط سوم عدد صحیح و نامنفی n می‌أید که تعداد وضعیت‌های ممنوعه است. سپس در n خط بعدی،‌ در هر خط ۵ رقم داده می‌شود که یک وضعیت ممنوعه را توصیف می‌کنند. هر دو رقم متوالی با یک فاصله از هم جدا شده‌اند.

$$n \leq 10^5$$

خروجی

در تنها سطر خروجی حداقل گام‌های مورد نیاز برای رسیدن از وضعیت ابتدایی به وضعیت انتهایی(بدون استفاده از وضعیت‌های ممنوعه) را چاپ کنید. اگر رسیدن به وضعیت نهایی ممکن نبود عدد -1 را چاپ کنید.

مثال

ورودی نمونه ۱

1 1 1 1 1
0 0 0 0 0
5
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1

خروجی نمونه ۱

7

ورودی نمونه ۲

0 0 0 0 0
0 5 3 1 7
10
0 0 0 0 1
0 0 0 0 9
0 0 0 1 0
0 0 0 9 0
0 0 1 0 0
0 0 9 0 0
0 1 0 0 0
0 9 0 0 0
1 0 0 0 0
9 0 0 0 0

خروجی نمونه ۲

-1