Path

تودی (TooDee) یک سرزمین دو بُعدی مشبک شبیه دستگاه مختصات دکارتی است که در آن موجوداتی به نام پنبور (ترجمه‌ی Dee) زندگی می‌کنند. پنبورها موجوداتی کوچک مانند زنبور هستند با این تفاوت که آن‌ها دو بُعدی و بسیار متمدن هستند! هم‌چنین در تودی، برخلاف کندوهای هادی زنبورها که شش گوش هستند، کندوی پنبور‌ها مستطیلی شکل و با اضلاع موازی با محورهای مختصات می‌باشند – یعنی دقیقاً یا از شرق به غرب، یا از جنوب به شمال.

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

• اگر بر روی نقطه شبکه‌ایِ $(x,y)$ قرار داشته باشند، یکی از چهار نقطه‌ی شبکه‌ای همسایه یعنی $(x-۱,y)$ یا $(x,y-۱)$ یا $(x+۱,y)$ یا $(x,y+۱)$ را انتخاب کرده و به آن سمت می‌روند (نقطه‌ی شبکه‌ای، نقطه‌ای است که هر دو مختصاتش صحیح باشد).
• هیچ پنبوری نمی‌تواند وارد یک کندو شود.
• یک پنبور تنها زمانی می تواند جهت حرکتش را تغییر دهند که روی جداره یا گوشه‌ی یک کندو باشد.
• در آغاز پرواز و در اولین گام، هر یک از ۴ جهت اصلی قابل انتخاب است.

امشب جشنِ تولدِ دخترِ سرکار خانم «پَفسَر» (یک افسر ارشد وزارت رفاه اجتماعی تودی) است. از همین رو، او می‌خواهد امشب خود را هر چه سریع‌تر به خانه‌اش برساند. با فرض آن‌که سرعت پرواز پفسر یک واحد طول در ثانیه می‌باشد، مسیری برای او پیدا کنید که بتواند ضمن رعایت کردن قوانین بالا، در کوتاه‌ترین زمان ممکن به خانه‌اش برسد.

• خط اوّل ورودی شامل یک عدد صحیح $T$ است که تعداد سناریوها را نشان می‌دهد و همواره $1 \leq T \leq 20$ است.
• در ادامه این $T$ سناریو پشت سر هم آمده‌اند. پیش از هر سناریو یک خط خالی در ورودی وجود دارد.
• خط اول هر سناریو حاوی چهار عدد صحیح است که با فاصله از هم جدا شده اند. دو عدد صحیح اول، مختصات $X$ و $Y$ محل کار و دو عدد صحیح دوم، مختصات خانه پفسر را بیان می‌کنند. خط دوم سناریو تعداد کندوها $N$ را مشخص می‌کند.
• در $N$ خط بعدی، در هر خط محل قرارگیری و اندازه‌ی یک کندو به‌وسیله‌ی مختصات دو تا گوشه‌ی روبه‌روی هم آن کندو داده می‌شود. می‌توانید فرض کنید هیچ دو‌کندویی هیچ تماس، هم‌پوشانی و یا حتی نقطه‌ی مشترکی، حتی در گوشه‌ها ندارند. مختصات محل کار و خانه‌ی پفسر متمایز می‌باشند. مساحت هر کندو حداقل یک واحد مربع می‌باشد.
• در تمامی سناریوهای ورودی، تمام مختصات‌ها صحیح بوده و در بازه‌ی $[-10^9, 10^9]$ قرار دارند. هم‌چنین $0\leq N \leq 1000$ است.
• در ۲۰ درصد تست‌ها، در تمامی سناریوهای تست $N\leq 10$ بوده و مختصات‌ها نامنفی و کم‌تر از $100$ هستند.
• در ۶۰ درصد تست‌ها، در تمامی سناریوهای تست، قدرمطلق مختصات کمتر از $1000$ بوده و $0\leq N \leq 100$ خواهد بود.

به‌همان ترتیب ورودی سناریو‌ها، به ازای هر سناریو، حداقل زمانِ مورد نیاز به ثانیه برای رسیدن پفسر به خانه را در خروجی چاپ کنید. اگر هیچ مسیر مجازی برای رفتن پفسر از محل کار به خانه‌اش وجود ندارد، در خروجی عبارت No Path را چاپ کنید.

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

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