+ محدودیت زمان: ۳.۵ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- مارچلو که سال سختی را سپری کرده، بسیار خسته است. پس تصمیم گرفته که در این تابستان قوای از دست رفتهٔ خود را بازیابی کند و چه کاری بهتر از یک مسافرت خوب و مقداری جهانگردی! زمینی که مارچلو در آن زندگی می‌کند تخت است! به طور دقیق‌تر جدولی $n \times m$ می‌باشد که هر خانه‌ی آن یا منطقه‌ی آزاد است و یا توسط کشوری اداره می‌شود. (توجه کنید لزومی ندارد مناطق تحت کنترل یک کشور مجاور یکدیگر باشند) او در هر مرحله می‌تواند به یکی از خانه‌های مجاور ضلعی خانه‌ی فعلی سفر کند. همچنین سفر در مناطق آزاد برای همگان مجاز است اما برای سفر در مناطق یک کشور نیاز به پاسپورت آن کشور داریم. هر کشور نیز تعدادی سفارت در مناطق آزاد دارد که می‌توان پاسپورت آن کشور را از آن‌ها اخذ کرد. با دریافت پاسپورت جدید پاسپورت قدیمی از بین خواهد رفت. **گرفتن پاسپورت یک کشور هیچ هزینه‌ای ندارد اما برای وارد شدن از منطقه‌ی آزاد به منطقه‌ی آن کشور باید یک واحد هزینه‌ی عوارض ورود بپردازیم.** حال مارچلو می‌خواهد از خانه‌ی خود در جدول شروع کند و مسافرتش را در خانه‌ی مقصدی که از قبل معلوم کرده به پایان برساند. به او کمک کنید با کمترین هزینه سفرش را انجام دهد. (یا بگویید که نمی‌تواند به مقصد برسد) **تضمین می‌شود خانه‌ی مارچلو در منطقه‌ی آزاد است و در ابتدا پاسپورت هیچ کشوری را ندارد.** # ورودی در خط اول به ترتیب اعداد $n, m, k$ آمده است که نشان دهنده‌ی طول جدول، عرض جدول و تعداد سفارت‌ها است. در خط دوم اعداد $ s_x, s_y, e_x, e_y $ آمده که مختصات خانه‌ی شروع و پایان مارچلو است. $$1 \le n, m \le 500$$ $$1 \le k \le 10^6$$ $$1 \le s_x, e_x \le n$$ $$1 \le s_y, e_y \le m$$ **تصمین می‌شود خانه‌ی ابتدایی و انتهایی یکی نیستند و تمام سفارت‌ها در مناطق آزاد هستند.** در هر یک از $n$ خط بعدی $m$ عدد آمده که عدد $j$ام در سطر $i$ام برابر با $a_{i,j}$ و نشان دهنده‌ی کشوری است که خانه‌ی $(i, j)$ را اداره می‌کند. (اگر این عدد صفر باشد، به این معناست که آن خانه منطقه‌ی آزاد است) $$0 \le a_{i,j} \le 10^6$$ سپس در هر یک از $k$ خط بعدی سه عدد $x, y, p$ آمده که نشان دهنده‌ی وجود سفارت کشور $p$ در خانه‌ی $(x, y)$ است. $$1 \le x \le n$$ $$1 \le y \le m$$ $$1 \le p \le 10^6$$ # خروجی اگر رسیدن به مقصد ممکن نبود `-1` و در غیر این صورت کمینه هزینه‌ی ممکن برای رسیدن به مقصد را چاپ کنید. ## ورودی نمونه ۱ ``` 4 4 2 1 1 4 4 0 0 1 2 0 2 2 2 0 1 1 2 1 1 1 2 1 2 1 2 1 2 ``` ## خروجی نمونه ۱ ``` 1 ``` می‌توان با گرفتن پاسپورت کشور ۲ در خانه‌ی $(1 ,2)$ و سپس رفتن به $(2 ,2)$ با یک هزینه وارد مناطق کشور ۲ شد و به مقصد رسید. ## ورودی نمونه ۲ ``` 4 4 1 1 1 4 4 0 0 1 2 0 2 2 2 1 1 0 0 1 1 1 2 1 2 2 ``` ## خروجی نمونه ۲ ``` 2 ``` مارچلو کافی است ابتدا پاسپورت کشور ۲ را در خانه‌ی $(1,2)$ بگیرد سپس با یک هزینه به $(2,2)$ رفته و با گذشت از $(2,3)$، $(3,3)$ و $(3,4)$ با یک هزینه وارد $(4,4)$ شده و به مقصد برسد. **توجه کنید تا زمانی که مارچلو پاسپورت جدیدی نگیرد پاسپورت قبلی‌اش برایش باقی می‌ماند.**

حل سؤال در بانک سؤالات