UT-alg-S94-CA3 چشم‌انداز شهر

Time Limit: 10 Seconds    Memory Limit: 32768 KB

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

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

و چشم انداز ساختمان‌های جدید:

پس از ترکیب، چشم‌انداز نهایی به این شکل خواهد بود:

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

Input

ورودی: خط اول، یک عدد صحیح و مثبت k۲۰ نوشته شده که برابر تعداد مجموعه‌های ورودی است. بعد از آن به ازاء هر مجموعه‌ی ورودی، در یک خط دو عدد n و m نوشته شده که n تعداد سطح‌ها در چشم‌انداز اول و m تعداد سطح‌ها در چشم‌انداز دوم است. بعد از این خط، در n خط بعدی، هر خط شامل دو عدد صحیح x و y برای نمایش نقطه‌ی ابتدای یک سطح از چشم‌انداز قدیم است. سپس در m خط بعدی، باز در هر خط دو عدد صحیح برای یک سطح از چشم‌انداز جدید نوشته شده. فرض کنید برای هر چشم‌انداز، x ها به شکل صعودی است و هیچ دو x متوالی، یا دو y متوالی برابر نیستند و در سطح آخر همیشه y=۰ است (توجه کنید که به‌جز سطح آخر، y بعضی از سطح‌های بینی هم ممکن است صفر باشد). فرض کنید n,m<۱۰۵ (کم‌تر از صدهزار) باشد. برنامه‌ی شما باید در کم‌تر از ۵ ثانیه (برروی کارگزار شِیرکد) به‌ازاء هر ورودی پاسخ را محاسبه کند.

Output

خروجی: به ازاء هر مجموعه‌ی ورودی، در یک خط عدد l و در خط بعدی 2l عدد برای نمایش چشم‌انداز ترکیب شده بنویسید.

Sample Input

1
6 3
15 10
21 18
27 10
30 0
42 18
53 0
10 20
24 14
58 0

Sample Output

6
10 20
24 18
27 14
42 18
53 14
58 0

Submit