- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
یک جنازه در پارک ملت پیدا شده است. طبق گفتههای پزشک قانونی، مقتول به وسیلهی شات-گان کشته شده و شلیک گلولهی شات-گان در یک لحظه بین لحظهی \(L\) و لحظهی \(R\) (شامل این دو لحظه) اتفاق افتاده است. کاراگاه شمس میخواهد حداقل و حداکثر تعداد ممکن برای افراد حاضر در پارک هنگام شلیک گلوله را بداند. همکار کارآگاه شمس، مادام، لیستی از مظنونین تهیه کرده و طی بازپرسی متوجه شده که مظنون \(i\)ام از لحظهی \(l_i\) تا لحظهی \(r_i\) (شامل این دو لحظه)، در پارک حضور داشته است. مادام میخواهد با استفاده از این اطلاعات اعداد مدنظر کاراگاه شمس را به او بگوید. البته این کار سادهای نیست، پس به او کمک کنید!
شلیک میتواند در لحظهای اعشاری اتفاق بیفتد.
ورودی
خط اول ورودی شامل دو عدد \(L\) و \(R\) است.
خط دوم شامل عدد \(n\) است که بیانگر تعداد مظنونین واقعه میباشد. سپس در \(n\) خط بعد هریک شامل دو عدد \(l_i\) و \(r_i\) است.
\[0 \le L \le R \le 10^9\]
\[0 \le l_i \le r_i \le 10^9\]
\[1 \le n \le 5000\]
خروجی
تنها خط خروجی باید شامل دو عدد باشد که برابر با کمترین و بیشترین تعداد ممکن برای افراد حاضر در لحظهی شلیک شات-گان هستند.
مثال
ورودی نمونه ۱
6 10
4
1 8
6 8
7 10
8 9
خروجی نمونه ۱
1 4