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

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

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

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

خط اول شامل یک عدد $T (1 \le T \le 20)$ تعداد سناریوهای مختلف است. $T$ بلوک که هر بلوک مربوط به یک سناریو است به شکل زیر داده می‌شود.

خط اول هر بلوک،‌ شامل دو عدد $R$ و $C$ $(1 \le R, C \le 50)$، که به ترتیب تعداد سطرها و ستون‌های جدول است. هر یک از $R$ خط بعدی، شامل $C$ عدد صحیح نامنفی،‌ $0 \le H_{i, j} \le 1000$،‌ است که ارتفاع ساختمان‌ها را مشخص می‌کنند. اولین عدد مربوط چپ‌ترین ساختمان در بالاترین سطر است. سپس مختصات نقاط شروع و پایان نوشته شده است. مختصات پایین‌ترین و راست‌ترین تقاطع $(R, C)$ است و مختصات تقاطع مقابلش(بالاترین و چپ‌ترین تقاطع)‌ $(0, 0)$ است.

در ادامه $A(0 \le A \le 100)$ می‌آید که تعداد آنتن‌هاست. $A$ خط بعدی آنتن‌ها را با سه عدد $r$،‌ $c (0 \le r \le R, 0 \le c \le C)$،‌ و $h(0 \le h \le 1000)$ مشخص می‌کند که به این معنی است که آنتی با ارتفاع $h$ در تقاطع $(r, c)$ قرار دارد.

برای هر سناریو در یک خط یک عدد بنویسید که کم‌ترین طولی به متر است که پروفسور پیش از رسیدن به مسابقه باید بپیماید. اگر چنین کاری ممکن نیست و دوست پروفسور باید راه دیگری برای گفتن مسیر به پروفسور انتخاب کنید،‌ $-1$ چاپ کنید.

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

• سوال قبل