====== ژنراتور ======


پس از اتفاق ناگوار قطع شدن برق باشگاه دانش‌پژوهان جوان در طول امتحان عملی اصلی دوم، مسئول برگزاری دوره تابستانی، آقای آ.ن.ش به مدیریت باشگاه دانش‌پژوهان جوان پیشنهاد دادند برای پیشگیری از این واقعه دلخراش در امتحانات پایانی، باشگاه اقدام به خرید یک ژنراتور برق  برای تولید برق مورد نیاز کامپیوترها نماید. متأسفانه این پیشنهاد از طرف مدیریت باشگاه به دلایلی‎) ‎گویا قیمت یک ژنراتور که برق ‎۳۰‎ کامپوتر را فراهم می‌کند از قیمت ‎۳۰‎ ژنراتور که هرکدام برق یک کامپیوتر را فراهم می‌کنند بیش‌تر است‎!‎) رد شد. از آنجا که آقای آ.ن.ش هرگز ناامید نمی‌شود بالاخره توانست هزینه خرید ژنراتور را با قبول پذیرش آگهی‌های یک اسپانسر خیّر ‎(!)‎ در گوشه‌ی دفترچه سوالات مرحله اول سال آینده بدست آورد و حتی بودجه مورد نیاز برای ساخت یک نیروگاه دائمی در کنار حیاط باشگاه را تأمین کند و باشگاه دانش پژوهان جوان را به خودکفایی مالی برساند‎.

هنگامی که آقای آ.ن.ش می‌خواست برای خرید ژنراتور اقدام کند متوجه شد که ژنراتوری با این قیمت هنگفت می‌بایست اندازه‌ی بسیار بزرگی داشته باشد و حمل کردن آن از درب ورودی 
ساختمان باشگاه ‎)‎بالای پله‌های حیاط‍، کنار عکس مرحوم پروفسور حسابی) تا پشت بام ساختمان (پله‌‎های فلزی پشت سر judge) از داخل راهرو و راه‌پله‌ها حمل شود.

پس از پرس و جوی فراوان آقای آ.ن.ش متوجه شد که همه ژنراتورهای موجود در بازار به شکل مکعب مربع هستند. برای راحتی کار، راهروی باشگاه از درب ورودی تا درب پشت بام را به صورت یک تونل دو بعدی فرض کرده (که از کنار به آن نگاه می‌کنیم) و هم‌چنین ژنراتور را نیز به‌صورت یک ‎ **مربع** دو بعدی فرض می‌کنیم.
حال آقای آ.ن.ش می‌خواهد بداند طول ضلع ژنراتور حداکثر چقدر می‌تواند باشد تا بتوان آن را از درب ورودی تا پشت بام حمل کرد. 

آقای آ.ن.ش از شما می‌خواهد تا این مسئله را حل کنید. نقاط کف و سقف راهرو به ترتیب 
در ورودی داده می‌شوند. اتصال نقاطِ متوالیِ سقف و کفِ راهرو، دیواره‌هایِ سقف و کفِ راهرو را تشکیل می‌دهند و شکل کف و سقف ساختمان بدست می‌آید که به صورت دو سطح یکی در پایین (کف راهرو) و یکی در بالای آن (سقف راهرو) قرار دارد.

کف راهرو با ‎$n$‎ نقطه بصورت ‎$(a_1,b_1),(a_2,b_2),...(a_n,b_n)$‎ و سقف راهرو با ‎$m$‎ نقطه بصورت $(c_1,d_1),(c_2,d_2),...(c_m,d_m)$‎ مشخص شده اند که ‎$a_i$‎ ها و ‎$c_i$‎ ها مختصات افقی (یا همان ‎$X$‎) در صفحه‌ی مختصات هستند. ‎$b_i$‎ ها و ‎$d_i$‎ ها مختصات عمودی (یا همان ‎($Y$‎ هستند.


به ازای هر ‎$1\leq i <n$‎ داریم: 
‎ $a_i\leq a_{i+1}$ ‎ و ‎ $b_i\leq b_{i+1}$ ‎


همین‌طور به ازای هر ‎$1\leq j <m$‎ داریم: 
‎ $c_i\leq c_{i+1}$  ‎ و  $d_i\leq d_{i+1}$ ‎


یعنی نقاط کف راهرو از چپ به راست و از پایین به بالا صعودی  و نقاط سقف راهرو نیز به همین صورت صعودی‌اند.


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


یعنی به ازای هر ‎$1\leq i <n$‎ یکی (یا هردو) عبارت زیر برقرار است:

$a_i = a_{i+1}$ یا $b_i=b_{i+1}$


همین‌طور به ازای هر ‎$1\leq j <m$‎ یکی (یا هردو) عبارت زیر برقرار است:



$c_i = c_{i+1}$ یا $d_i=d_{i+1}$


نقطه‌ی ابتدایی سقف و نقطه‌ی ابتدایی کف راهرو مختصات افقی برابر دارند. نقطه انتهایی سقف و  نقطه انتهایی کف هم مختصات افقی برابر دارند. نقطه‌ی ابتدایی سقف و کف، درب ساختمان هستند و  ژنراتور باید از بین این دو نقطه از چپ به راست عبور کند و بعد از عبور از راهرو از بین نقطه‌ی انتهایی سقف و نقطه‌ی انتهایی کف (درب پشت بام) از چپ به راست عبور کند. اضلاع ژنراتور که به صورت مربع است در طول راه می‌بایست همواره موازی محورهای مختصات باشند و ژنراتور را نمی‌توان چرخاند. ژنراتور می‌تواند با دیوارها تماس پیدا کند ولی نباید از دیواره‌های سقف یا کف عبور کند. دیوارها را نمی‌توان تخریب کرد‎!‎

سقف راهرو هرگز با کف آن تماس پیدا نمی‌کند و مختصات نقاط راهرو صحیح هستند.




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

===== ‎ورودی =====
  * در سطر اول ورودی، عدد ‎$n$‎، تعداد نقاط‍ کف راهرو قرار دارد‎. ‎
  * در ‎$n$‎ سطر بعدی، در سطر ‎$i+1$‎ام به ترتیب دو عدد ‎$a_i$‎ و ‎$b_i$ (مختصات نقطه‌ی ‎$i$‎ام کف راهرو) آمده است. 
  * سپس در خط ‎$n+2$‎ام عدد ‎$m$‎ قرار دارد و در ‎$m$‎ سطر بعدی، در سطر ‎$n+2+j$ام به ترتیب ‎$c_j$‎ و ‎$d_j$ (مختصات نقطه‌ی ‎$j$‎ام سقف راهرو) آمده‌اند.
  * همواره ‎$2 \le n,m \le 10^6$‎ و در حداقل ‎$20$‎ درصد تست‌ها ‎$n$‎ و ‎$m$‎ از ‎$1000$‎ بیش‌تر نیستند.
  * همواره ‎$\leq 10^9$‎مختصات نقاط‎$-10^9\leq$‎ و در حداقل ‎$60$ درصد تست‌ها ‎$\leq 10^5$‎ مختصات نقاط ‎$-10^5 \leq$‎

===== ‎خروجی =====

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


===== محدودیت‌ها =====


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


===== ورودي و خروجي نمونه =====

<WRAP :en>
^  ورودي نمونه  ^  خروجي نمونه  ^
|6 \\ ‎1 1 \\ ‎7 1 \\ ‎9 1 \\ ‎9 9 \\ ‎11 9 \\ ‎21 9 \\ 4 \\ ‎1 6 \\ ‎7 6 \\ ‎7 13 \\ ‎21 13|‎2‎|
|‎8 \\ ‎0 0 \\ ‎5 0 \\ 5 2 \\ ‎‎7 2 \\ 7 6 \\ ‎10 6 \\ ‎10 7 \\ ‎12 7 \\ 9 \\ ‎0 5 \\ ‎2 5 \\ ‎2 7 \\ ‎4 7 \\ ‎4 9 \\ ‎7 9 \\ ‎7 10 \\ ‎11 10 \\ ‎12 10‎|‎3‎‎|
</WRAP>
شکل زیر مربوط به این مثال است:
{{ :سوالات_المپیاد:دوره‌ی_تابستان:دوره‌ی_۱۸:عملی:ژنراتور.png |}}
  * [[سوال ۱۳|سوال قبل]]