시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB20141191.667%

문제

UDPC 나라의 통신 설비를 담당하는 윤이는 직선 도로를 따라 $N$개의 송신탑을 설치하려고 한다.

윤이의 역할은 송신탑 사이에 전파 간섭이 일어나지 않도록 송신탑의 위치와 전파 우선순위를 설정하는 일이다. 송신탑에는 $1$번부터 $N$번까지 번호가 붙어 있으며, 번호 순서대로 왼쪽에서 오른쪽으로 설치해야 한다. $1$번 송신탑의 좌표는 $0$으로 고정한다. 송신탑의 전파 우선순위로는 $1$ 이상 $N$ 이하의 서로 다른 정수를 배정해야 한다.

송신탑이 전파 간섭을 일으키는 상황은 다음과 같다. $i$번 송신탑이 설치된 좌표를 $x_i$라고 하면, 전파 간섭을 일으킬 수 있는 범위는 $(x_i-L_i, x_i+R_i)$ 구간이다. 구간의 양 끝은 간섭 범위에 포함되지 않는다. $i$번 송신탑의 전파 우선순위를 $p_i$라고 할 때, $i$번 송신탑의 간섭 범위 안에 $p_i < p_j$인 $j$번 송신탑이 존재하면 전파 간섭이 발생한다.

윤이는 각 송신탑의 위치와 전파 우선순위를 적절히 설정하여 $1$번 송신탑과 $N$번 송신탑 사이의 거리를 최소화하려고 한다. 조건을 만족하도록 송신탑을 설치하는 방법을 찾으시오.

입력

첫째 줄에 송신탑의 개수 $N$이 주어진다. $(1 \le N \le 300\,000)$

다음 $N$개 줄의 $i$번째 줄에는 $i$번 송신탑의 간섭 범위를 나타내는 정수 $L_i$, $R_i$가 공백으로 구분되어 주어진다. $(1 \le L_i, R_i \le 10^9)$

출력

총 $N$개의 줄을 출력한다. $i$번째 줄에는 $i$번 송신탑의 좌표와 전파 우선순위를 공백으로 구분하여 출력한다.

가능한 답이 여러 가지이면 하나만 출력한다.

예제 입력 1

4
1 5
3 4
10 2
4 2

예제 출력 1

0 2
3 1
7 3
9 4

예제 입력 2

6
3 10
1 2
1 1
5 2
8 1
2 1

예제 출력 2

0 6
1 2
2 1
5 3
8 4
9 5
W3sicHJvYmxlbV9pZCI6IjM1NDc1IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVjMWExXHVjMmUwXHVkMGQxIFx1YzEyNFx1Y2U1OCIsImRlc2NyaXB0aW9uIjoiPHA+VURQQyBcdWIwOThcdWI3N2NcdWM3NTggXHVkMWI1XHVjMmUwIFx1YzEyNFx1YmU0NFx1Yjk3YyBcdWIyZjRcdWIyZjlcdWQ1NThcdWIyOTQgXHVjNzI0XHVjNzc0XHViMjk0IFx1YzljMVx1YzEyMCBcdWIzYzRcdWI4NWNcdWI5N2MgXHViNTMwXHViNzdjICROJFx1YWMxY1x1Yzc1OCBcdWMxYTFcdWMyZTBcdWQwZDFcdWM3NDQgXHVjMTI0XHVjZTU4XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzI0XHVjNzc0XHVjNzU4IFx1YzVlZFx1ZDU2MFx1Yzc0MCBcdWMxYTFcdWMyZTBcdWQwZDEgXHVjMGFjXHVjNzc0XHVjNWQwIFx1YzgwNFx1ZDMwYyBcdWFjMDRcdWMxMmRcdWM3NzQgXHVjNzdjXHVjNWI0XHViMDk4XHVjOWMwIFx1YzU0YVx1YjNjNFx1Yjg1ZCBcdWMxYTFcdWMyZTBcdWQwZDFcdWM3NTggXHVjNzA0XHVjZTU4XHVjNjQwIFx1YzgwNFx1ZDMwYyBcdWM2YjBcdWMxMjBcdWMyMWNcdWM3MDRcdWI5N2MgXHVjMTI0XHVjODE1XHVkNTU4XHViMjk0IFx1Yzc3Y1x1Yzc3NFx1YjJlNC4gXHVjMWExXHVjMmUwXHVkMGQxXHVjNWQwXHViMjk0ICQxJFx1YmM4OFx1YmQ4MFx1ZDEzMCAkTiRcdWJjODhcdWFlNGNcdWM5YzAgXHViYzg4XHVkNjM4XHVhYzAwIFx1YmQ5OVx1YzViNCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YmM4OFx1ZDYzOCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjNjdjXHVjYWJkXHVjNWQwXHVjMTFjIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWMxMjRcdWNlNThcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiAkMSRcdWJjODggXHVjMWExXHVjMmUwXHVkMGQxXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCAkMCRcdWM3M2NcdWI4NWMgXHVhY2UwXHVjODE1XHVkNTVjXHViMmU0LiBcdWMxYTFcdWMyZTBcdWQwZDFcdWM3NTggXHVjODA0XHVkMzBjIFx1YzZiMFx1YzEyMFx1YzIxY1x1YzcwNFx1Yjg1Y1x1YjI5NCAkMSQgXHVjNzc0XHVjMGMxICROJCBcdWM3NzRcdWQ1NThcdWM3NTggXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWM4MTVcdWMyMThcdWI5N2MgXHViYzMwXHVjODE1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMWExXHVjMmUwXHVkMGQxXHVjNzc0IFx1YzgwNFx1ZDMwYyBcdWFjMDRcdWMxMmRcdWM3NDQgXHVjNzdjXHVjNzNjXHVkMGE0XHViMjk0IFx1YzBjMVx1ZDY2OVx1Yzc0MCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LiAkaSRcdWJjODggXHVjMWExXHVjMmUwXHVkMGQxXHVjNzc0IFx1YzEyNFx1Y2U1OFx1YjQxYyBcdWM4OGNcdWQ0NWNcdWI5N2MgJHhfaSRcdWI3N2NcdWFjZTAgXHVkNTU4XHViYTc0LCBcdWM4MDRcdWQzMGMgXHVhYzA0XHVjMTJkXHVjNzQ0IFx1Yzc3Y1x1YzczY1x1ZDBhYyBcdWMyMTggXHVjNzg4XHViMjk0IFx1YmM5NFx1YzcwNFx1YjI5NCAkKHhfaS1MX2ksIHhfaStSX2kpJCBcdWFkNmNcdWFjMDRcdWM3NzRcdWIyZTQuIFx1YWQ2Y1x1YWMwNFx1Yzc1OCBcdWM1OTEgXHViMDVkXHVjNzQwIFx1YWMwNFx1YzEyZCBcdWJjOTRcdWM3MDRcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gJGkkXHViYzg4IFx1YzFhMVx1YzJlMFx1ZDBkMVx1Yzc1OCBcdWM4MDRcdWQzMGMgXHVjNmIwXHVjMTIwXHVjMjFjXHVjNzA0XHViOTdjICRwX2kkXHViNzdjXHVhY2UwIFx1ZDU2MCBcdWI1NGMsICRpJFx1YmM4OCBcdWMxYTFcdWMyZTBcdWQwZDFcdWM3NTggXHVhYzA0XHVjMTJkIFx1YmM5NFx1YzcwNCBcdWM1NDhcdWM1ZDAgJHBfaSAmbHQ7IHBfaiRcdWM3NzggJGokXHViYzg4IFx1YzFhMVx1YzJlMFx1ZDBkMVx1Yzc3NCBcdWM4NzRcdWM3YWNcdWQ1NThcdWJhNzQgXHVjODA0XHVkMzBjIFx1YWMwNFx1YzEyZFx1Yzc3NCBcdWJjMWNcdWMwZGRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzcyNFx1Yzc3NFx1YjI5NCBcdWFjMDEgXHVjMWExXHVjMmUwXHVkMGQxXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YzY0MCBcdWM4MDRcdWQzMGMgXHVjNmIwXHVjMTIwXHVjMjFjXHVjNzA0XHViOTdjIFx1YzgwMVx1YzgwOFx1ZDc4OCBcdWMxMjRcdWM4MTVcdWQ1NThcdWM1ZWMgJDEkXHViYzg4IFx1YzFhMVx1YzJlMFx1ZDBkMVx1YWNmYyAkTiRcdWJjODggXHVjMWExXHVjMmUwXHVkMGQxIFx1YzBhY1x1Yzc3NFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWI5N2MgXHVjZDVjXHVjMThjXHVkNjU0XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjODcwXHVhYzc0XHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjNjNFx1Yjg1ZCBcdWMxYTFcdWMyZTBcdWQwZDFcdWM3NDQgXHVjMTI0XHVjZTU4XHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0NCBcdWNjM2VcdWM3M2NcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzFhMVx1YzJlMFx1ZDBkMVx1Yzc1OCBcdWFjMWNcdWMyMTggJE4kXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJCgxIFxcbGUgTiBcXGxlIDMwMFxcLDAwMCkkPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyAkTiRcdWFjMWMgXHVjOTA0XHVjNzU4ICRpJFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgJGkkXHViYzg4IFx1YzFhMVx1YzJlMFx1ZDBkMVx1Yzc1OCBcdWFjMDRcdWMxMmQgXHViYzk0XHVjNzA0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWM4MTVcdWMyMTggJExfaSQsICRSX2kkXHVhYzAwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAkKDEgXFxsZSBMX2ksIFJfaSBcXGxlIDEwXjkpJDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2QxZCAkTiRcdWFjMWNcdWM3NTggXHVjOTA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gJGkkXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCAkaSRcdWJjODggXHVjMWExXHVjMmUwXHVkMGQxXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YzY0MCBcdWM4MDRcdWQzMGMgXHVjNmIwXHVjMTIwXHVjMjFjXHVjNzA0XHViOTdjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NThcdWM1ZWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDBcdWIyYTVcdWQ1NWMgXHViMmY1XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWM3NzRcdWJhNzQgXHVkNTU4XHViMDk4XHViOWNjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIzNTQ3NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJhZGlvIFRvd2VyIEluc3RhbGxhdGlvbiIsImRlc2NyaXB0aW9uIjoiPHA+WXVuZWUsIHdobyBpcyBpbiBjaGFyZ2Ugb2YgY29tbXVuaWNhdGlvbiBpbmZyYXN0cnVjdHVyZSBpbiB0aGUgY291bnRyeSBvZiBVRFBDLCBpcyBwbGFubmluZyB0byBpbnN0YWxsICROJCByYWRpbyB0b3dlcnMgYWxvbmcgYSBzdHJhaWdodCByb2FkLjxcL3A+XHJcblxyXG48cD5ZdW5lZSZyc3F1bztzIHRhc2sgaXMgdG8gY2hvb3NlIHRoZSBwb3NpdGlvbnMgYW5kIHNpZ25hbCBwcmlvcml0aWVzIG9mIHRoZSB0b3dlcnMgc28gdGhhdCBubyByYWRpbyBpbnRlcmZlcmVuY2Ugb2NjdXJzIGJldHdlZW4gdGhlbS4gVGhlIHRvd2VycyBhcmUgbnVtYmVyZWQgZnJvbSAkMSQgdG8gJE4kLCBhbmQgdGhleSBtdXN0IGJlIGluc3RhbGxlZCBmcm9tIGxlZnQgdG8gcmlnaHQgaW4gdGhhdCBvcmRlci4gVGhlIGNvb3JkaW5hdGUgb2YgdG93ZXIgJDEkIGlzIGZpeGVkIGF0ICQwJC4gQXMgc2lnbmFsIHByaW9yaXRpZXMsIGRpc3RpbmN0IGludGVnZXJzIGZyb20gJDEkIHRocm91Z2ggJE4kIG11c3QgYmUgYXNzaWduZWQuPFwvcD5cclxuXHJcbjxwPlJhZGlvIGludGVyZmVyZW5jZSBvY2N1cnMgaW4gdGhlIGZvbGxvd2luZyBzaXR1YXRpb24uIExldCB0aGUgY29vcmRpbmF0ZSBvZiB0b3dlciAkaSQgYmUgJHhfaSQuIFRoZW4gdGhlIHJhbmdlIGluIHdoaWNoIGl0IGNhbiBjYXVzZSBpbnRlcmZlcmVuY2UgaXMgdGhlIGludGVydmFsICQoeF9pLUxfaSx4X2krUl9pKSQuIFRoZSBlbmRwb2ludHMgb2YgdGhlIGludGVydmFsIGFyZSBub3QgaW5jbHVkZWQgaW4gdGhlIGludGVyZmVyZW5jZSByYW5nZS4gTGV0IHRoZSBzaWduYWwgcHJpb3JpdHkgb2YgdG93ZXIgJGkkIGJlICRwX2kkLiBJZiB0aGVyZSBleGlzdHMgYSB0b3dlciAkaiQgd2l0aCAkcF9pJmx0O3BfaiQgaW5zaWRlIHRoZSBpbnRlcmZlcmVuY2UgcmFuZ2Ugb2YgdG93ZXIgJGkkLCB0aGVuIHJhZGlvIGludGVyZmVyZW5jZSBvY2N1cnMuPFwvcD5cclxuXHJcbjxwPll1bmVlIHBsYW5zIHRvIGNob29zZSB0aGUgcG9zaXRpb25zIGFuZCBzaWduYWwgcHJpb3JpdGllcyBvZiB0aGUgdG93ZXJzIGFwcHJvcHJpYXRlbHkgc28gdGhhdCB0aGUgZGlzdGFuY2UgYmV0d2VlbiB0b3dlciAkMSQgYW5kIHRvd2VyICROJCBpcyBtaW5pbWl6ZWQuIEZpbmQgYSB3YXkgdG8gaW5zdGFsbCB0aGUgdG93ZXJzIHRoYXQgc2F0aXNmaWVzIHRoZSBjb25kaXRpb25zLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdGhlIG51bWJlciBvZiByYWRpbyB0b3dlcnMgJE4kLiAkKDFcXGxlIE5cXGxlIDMwMFxcLCAwMDApJDxcL3A+XHJcblxyXG48cD5UaGUgJGkkLXRoIG9mIHRoZSBuZXh0ICROJCBsaW5lcyBjb250YWlucyB0d28gc3BhY2Utc2VwYXJhdGVkIGludGVnZXJzICRMX2kkIGFuZCAkUl9pJCwgcmVwcmVzZW50aW5nIHRoZSBpbnRlcmZlcmVuY2UgcmFuZ2Ugb2YgdG93ZXIgJGkkLiAkKDFcXGxlIExfaSxSX2lcXGxlIDEwXjkpJDxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IGEgdG90YWwgb2YgJE4kIGxpbmVzLiBPbiB0aGUgJGkkLXRoIGxpbmUsIHByaW50IHRoZSBjb29yZGluYXRlIGFuZCBzaWduYWwgcHJpb3JpdHkgb2YgdG93ZXIgJGkkLCBzZXBhcmF0ZWQgYnkgYSBzcGFjZS48XC9wPlxyXG5cclxuPHA+SWYgdGhlcmUgYXJlIG11bHRpcGxlIHZhbGlkIGFuc3dlcnMsIHByaW50IGFueSBvbmUgb2YgdGhlbS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d