문제
UNIST 근처의 직선 고속도로에는 과속 차량을 감지하기 위한 과속카메라가 있다. 이 과속카메라는 다음과 같은 원리로 차량의 속도를 측정한다.
차량이 감지 범위 내에 진입하면, $N$개의 서로 다른 시각에 차량의 위치를 촬영한다. 이 과속카메라는 움직이는 물체의 정확한 위치를 측정하지는 못하지만, 각 사진마다 차량의 좌표 범위를 알 수 있다. $i$번째 사진은 차량의 좌표가 $l_i$ 이상 $r_i$ 이하라는 정보를 담고 있다. 과속카메라는 촬영한 $N$장의 사진 정보를 통해서 차량의 최소 속도와 최대 속도를 계산할 수 있다. 측정하는 동안 차량의 속도는 항상 일정하다고 가정하며, 속도는 음수가 될 수도 있다.
어느 날, 고속도로를 신나게 달리던 윤이는 과속카메라에 자신이 찍힌 것을 발견했다. 벌금이 두려웠던 윤이는 과속카메라를 해킹해서 촬영된 사진들과 과속카메라 소프트웨어를 지워버렸다. 당신의 목표는 과속카메라가 정상 작동할 수 있도록 과속카메라의 소프트웨어를 복원하는 것이다.
출력
과속카메라가 측정한 차량의 최소 속도와 최대 속도를 공백으로 구분하여 출력한다. 절대/상대 오차는 10ドル^{-6}$까지 허용한다.
W3sicHJvYmxlbV9pZCI6IjI2MTI5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhY2ZjXHVjMThkXHVjZTc0XHViYTU0XHViNzdjIiwiZGVzY3JpcHRpb24iOiI8cD5VTklTVCBcdWFkZmNcdWNjOThcdWM3NTggXHVjOWMxXHVjMTIwIFx1YWNlMFx1YzE4ZFx1YjNjNFx1Yjg1Y1x1YzVkMFx1YjI5NCBcdWFjZmNcdWMxOGQgXHVjYzI4XHViN2M5XHVjNzQ0IFx1YWMxMFx1YzljMFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NWMgXHVhY2ZjXHVjMThkXHVjZTc0XHViYTU0XHViNzdjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YWNmY1x1YzE4ZFx1Y2U3NFx1YmE1NFx1Yjc3Y1x1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YzZkMFx1YjlhY1x1Yjg1YyBcdWNjMjhcdWI3YzlcdWM3NTggXHVjMThkXHViM2M0XHViOTdjIFx1Y2UyMVx1YzgxNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjYzI4XHViN2M5XHVjNzc0IFx1YWMxMFx1YzljMCBcdWJjOTRcdWM3MDQgXHViMGI0XHVjNWQwIFx1YzljNFx1Yzc4NVx1ZDU1OFx1YmE3NCwgJE4kXHVhYzFjXHVjNzU4IFx1YzExY1x1Yjg1YyBcdWIyZTRcdWI5NzggXHVjMmRjXHVhYzAxXHVjNWQwIFx1Y2MyOFx1YjdjOVx1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHVjZDJjXHVjNjAxXHVkNTVjXHViMmU0LiBcdWM3NzQgXHVhY2ZjXHVjMThkXHVjZTc0XHViYTU0XHViNzdjXHViMjk0IFx1YzZjMFx1YzljMVx1Yzc3NFx1YjI5NCBcdWJiM2NcdWNjYjRcdWM3NTggXHVjODE1XHVkNjU1XHVkNTVjIFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWNlMjFcdWM4MTVcdWQ1NThcdWM5YzBcdWIyOTQgXHViYWJiXHVkNTU4XHVjOWMwXHViOWNjLCBcdWFjMDEgXHVjMGFjXHVjOWM0XHViOWM4XHViMmU0IFx1Y2MyOFx1YjdjOVx1Yzc1OCBcdWM4OGNcdWQ0NWMgXHViYzk0XHVjNzA0XHViOTdjIFx1YzU0YyBcdWMyMTggXHVjNzg4XHViMmU0LiAkaSRcdWJjODhcdWM5ZjggXHVjMGFjXHVjOWM0XHVjNzQwIFx1Y2MyOFx1YjdjOVx1Yzc1OCBcdWM4OGNcdWQ0NWNcdWFjMDAgJGxfaSQgXHVjNzc0XHVjMGMxICRyX2kkIFx1Yzc3NFx1ZDU1OFx1Yjc3Y1x1YjI5NCBcdWM4MTVcdWJjZjRcdWI5N2MgXHViMmY0XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVhY2ZjXHVjMThkXHVjZTc0XHViYTU0XHViNzdjXHViMjk0IFx1Y2QyY1x1YzYwMVx1ZDU1YyAkTiRcdWM3YTVcdWM3NTggXHVjMGFjXHVjOWM0IFx1YzgxNVx1YmNmNFx1Yjk3YyBcdWQxYjVcdWQ1NzRcdWMxMWMgXHVjYzI4XHViN2M5XHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWMxOGRcdWIzYzRcdWM2NDAgXHVjZDVjXHViMzAwIFx1YzE4ZFx1YjNjNFx1Yjk3YyBcdWFjYzRcdWMwYjBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjZTIxXHVjODE1XHVkNTU4XHViMjk0IFx1YjNkOVx1YzU0OCBcdWNjMjhcdWI3YzlcdWM3NTggXHVjMThkXHViM2M0XHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWM3N2NcdWM4MTVcdWQ1NThcdWIyZTRcdWFjZTAgXHVhYzAwXHVjODE1XHVkNTU4XHViYTcwLCBcdWMxOGRcdWIzYzRcdWIyOTQgXHVjNzRjXHVjMjE4XHVhYzAwIFx1YjQyMCBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1YjRcdWIyOTAgXHViMGEwLCBcdWFjZTBcdWMxOGRcdWIzYzRcdWI4NWNcdWI5N2MgXHVjMmUwXHViMDk4XHVhYzhjIFx1YjJlY1x1YjlhY1x1YjM1OCBcdWM3MjRcdWM3NzRcdWIyOTQgXHVhY2ZjXHVjMThkXHVjZTc0XHViYTU0XHViNzdjXHVjNWQwIFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWNjMGRcdWQ3OGMgXHVhYzgzXHVjNzQ0IFx1YmMxY1x1YWNhY1x1ZDU4OFx1YjJlNC4gXHViYzhjXHVhZTA4XHVjNzc0IFx1YjQ1MFx1YjgyNFx1YzZlMFx1YjM1OCBcdWM3MjRcdWM3NzRcdWIyOTQgXHVhY2ZjXHVjMThkXHVjZTc0XHViYTU0XHViNzdjXHViOTdjIFx1ZDU3NFx1ZDBiOVx1ZDU3NFx1YzExYyBcdWNkMmNcdWM2MDFcdWI0MWMgXHVjMGFjXHVjOWM0XHViNGU0XHVhY2ZjIFx1YWNmY1x1YzE4ZFx1Y2U3NFx1YmE1NFx1Yjc3YyBcdWMxOGNcdWQ1MDRcdWQyYjhcdWM2ZThcdWM1YjRcdWI5N2MgXHVjOWMwXHVjNmNjXHViYzg0XHViODM4XHViMmU0LiBcdWIyZjlcdWMyZTBcdWM3NTggXHViYWE5XHVkNDVjXHViMjk0IFx1YWNmY1x1YzE4ZFx1Y2U3NFx1YmE1NFx1Yjc3Y1x1YWMwMCBcdWM4MTVcdWMwYzEgXHVjNzkxXHViM2Q5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIzYzRcdWI4NWQgXHVhY2ZjXHVjMThkXHVjZTc0XHViYTU0XHViNzdjXHVjNzU4IFx1YzE4Y1x1ZDUwNFx1ZDJiOFx1YzZlOFx1YzViNFx1Yjk3YyBcdWJjZjVcdWM2ZDBcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhY2ZjXHVjMThkXHVjZTc0XHViYTU0XHViNzdjXHVhYzAwIFx1Y2MwZFx1Yzc0MCBcdWMwYWNcdWM5YzRcdWM3NTggXHVjMjE4ICROJFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICQoMlxcbGUgTlxcbGUgMzAwXFwgMDAwKSQ8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjXHVjNWQwICROJFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzQgXHVjOTExICRpJFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMTM4IFx1YzgxNVx1YzIxOCAkdF9pJCwgJGxfaSQsICRyX2kkXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJGkkXHViYzg4XHVjOWY4IFx1YzBhY1x1YzljNFx1Yzc3NCBcdWNjMGRcdWQ3OGMgXHVjMmRjXHVhYzAxXHVjNzQwICR0X2kkXHVjNzc0XHViYTcwLCBcdWMwYWNcdWM5YzRcdWM1ZDBcdWMxMWMgXHVjYzI4XHViN2M5XHVjNzU4IFx1Yzg4Y1x1ZDQ1YyBcdWJjOTRcdWM3MDRcdWFjMDAgJFtsX2kscl9pXSRcdWM3ODRcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiAkdF9pJFx1YjI5NCBcdWM5OWRcdWFjMDBcdWQ1NThcdWIzYzRcdWI4NWQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDBcXGxlIHRfaVxcbGUgMTBeOSwwXFxsZSBsX2lcXGxlIHJfaVxcbGUgMTBeOSkkPFwvcD5cclxuXHJcbjxwPlx1ZDU2ZFx1YzBjMSBcdWIyZjVcdWM3NzQgXHVjODc0XHVjN2FjXHVkNTU4XHViMjk0IFx1Yzc4NVx1YjgyNVx1YjljYyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhY2ZjXHVjMThkXHVjZTc0XHViYTU0XHViNzdjXHVhYzAwIFx1Y2UyMVx1YzgxNVx1ZDU1YyBcdWNjMjhcdWI3YzlcdWM3NTggXHVjZDVjXHVjMThjIFx1YzE4ZFx1YjNjNFx1YzY0MCBcdWNkNWNcdWIzMDAgXHVjMThkXHViM2M0XHViOTdjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NThcdWM1ZWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM4MDhcdWIzMDBcL1x1YzBjMVx1YjMwMCBcdWM2MjRcdWNjMjhcdWIyOTQgJDEwXnstNn0kXHVhZTRjXHVjOWMwIFx1ZDVjOFx1YzZhOVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyNjEyOSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlNwZWVkIENhbWVyYSIsImRlc2NyaXB0aW9uIjoiPHA+QSBzdHJhaWdodCBoaWdod2F5IG5lYXIgVU5JU1QgaGFzIGEgc3BlZWQgY2FtZXJhIHRvIGRldGVjdCBzcGVlZGluZyB2ZWhpY2xlcy4gSXQgbWVhc3VyZXMgdGhlIHNwZWVkIG9mIHRoZSB2ZWhpY2xlIGluIHRoZSBmb2xsb3dpbmcgbWFubmVyLjxcL3A+XHJcblxyXG48cD5XaGVuIGEgdmVoaWNsZSBlbnRlcnMgYSBkZXRlY3Rpb24gcmFuZ2UsIHRoZSBjYW1lcmEgcGhvdG9ncmFwaHMgdGhlIGxvY2F0aW9ucyBvZiB0aGUgdmVoaWNsZSBhdCAkTiQgZGlmZmVyZW50IHRpbWVzLiBUaGlzIHNwZWVkIGNhbWVyYSBjYW5ub3QgbWVhc3VyZSB0aGUgZXhhY3QgcG9zaXRpb24gb2YgYSBtb3Zpbmcgb2JqZWN0LCBidXQgaXQgY2FuIGRldGVybWluZSB0aGUgcG9zaXRpb24gcmFuZ2Ugb2YgdGhlIHZlaGljbGUgaW4gZWFjaCBwaWN0dXJlLiBUaGUgJGkkLXRoIHBpY3R1cmUgY29udGFpbnMgaW5mb3JtYXRpb24gdGhhdCB0aGUgdmVoaWNsZSZyc3F1bztzIHBvc2l0aW9uIGlzIGJldHdlZW4gJGxfaSQgYW5kICRyX2kkLCBpbmNsdXNpdmUuIFRoZSBzcGVlZCBjYW1lcmEgdGhlbiBkZWR1Y2VzIHRoZSB2ZWxvY2l0eSByYW5nZSBvZiB0aGUgdmVoaWNsZSBiYXNlZCBvbiB0aGUgJE4kIHBpY3R1cmVzLiBUaGUgdmVsb2NpdHkgb2YgdGhlIHZlaGljbGUgaXMgYXNzdW1lZCB0byBiZSBjb25zdGFudCBkdXJpbmcgdGhlIG1lYXN1cmVtZW50LiBBbHNvLCB0aGUgdmVsb2NpdHkgY2FuIGJlIG5lZ2F0aXZlLjxcL3A+XHJcblxyXG48cD5PbmUgZGF5LCBZdW5lZSB3YXMgcnVubmluZyBvbiB0aGUgaGlnaHdheSBhbmQgbm90aWNlZCB0aGF0IFl1bmVlIGdvdCBjYXVnaHQgYnkgdGhlIHNwZWVkIGNhbWVyYS4gWXVuZWUgd2FzIGFmcmFpZCBvZiBwYXlpbmcgZmluZXMsIHNvIFl1bmVlIGhhY2tlZCB0aGUgc3BlZWQgY2FtZXJhIHRvIHJlbW92ZSBhbGwgdGhlIHBpY3R1cmVzIGFuZCB0aGUgc3BlZWQgY2FtZXJhIHNvZnR3YXJlLiBZb3VyIGdvYWwgaXMgdG8gcmVzdG9yZSB0aGUgc3BlZWQgY2FtZXJhIHNvZnR3YXJlIHRvIGZ1bmN0aW9uIG5vcm1hbGx5IGFnYWluLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgZ2l2ZXMgdGhlIG51bWJlciBvZiBwaWN0dXJlcyAkTiQgdGhhdCB0aGUgc3BlZWQgY2FtZXJhIHRha2VzLiAkKDJcXGxlIE5cXGxlIDMwMFxcIDAwMCkkPFwvcD5cclxuXHJcbjxwPlRoZW4gJE4kIGxpbmVzIGZvbGxvdy4gVGhlICRpJC10aCBsaW5lIGdpdmVzIHRocmVlIGludGVnZXJzICR0X2kkLCAkbF9pJCwgYW5kICRyX2kkLiBJdCByZXByZXNlbnRzIHRoYXQgdGhlICRpJC10aCBwaWN0dXJlIGlzIHRha2VuIGF0IHRpbWUgJHRfaSQsIGFuZCB0aGUgdmVoaWNsZSBwb3NpdGlvbiBpcyBpbiB0aGUgcmFuZ2UgJFtsX2kscl9pXSQgYXQgdGhhdCB0aW1lLiBUaGUgcGljdHVyZXMgYXJlIGdpdmVuIGluIGluY3JlYXNpbmcgb3JkZXIgb2YgJHRfaSQuICQoMFxcbGUgdF9pXFxsZSAxMF45LDBcXGxlIGxfaVxcbGUgcl9pXFxsZSAxMF45KSQ8XC9wPlxyXG5cclxuPHA+SXQgaXMgZ3VhcmFudGVlZCB0aGF0IHRoZXJlIGV4aXN0cyBhIHZhbGlkIHZlaGljbGUgdmVsb2NpdHkgZm9yIHRoZSBpbnB1dHMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBtaW5pbXVtIGFuZCBtYXhpbXVtIHBvc3NpYmxlIHZlbG9jaXR5IG9mIHRoZSB2ZWhpY2xlIGluIG9uZSBsaW5lLiBUaGUgYW5zd2VyIHdpbGwgYmUgY29uc2lkZXJlZCBhcyBjb3JyZWN0IGlmIGl0IGhhcyBhbiBhYnNvbHV0ZSBvciByZWxhdGl2ZSBlcnJvciBsZXNzIHRoYW4gJDEwXnstNn0kLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=