시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB118927720822.584%

문제

옛날 옛날에, 아름다운 몰다비아의 지역에 1부터 N까지 고유한 번호가 붙여진 N개의 중세 도시가 있었다. 번호 1이 붙여진 도시는 수도이다. 도시들은 N-1개의 양방향 도로로 연결되어 있으며, 각 도로는 킬로미터 단위의 길이를 가지고 있다.

도시를 두 번 거치지 않고 도시의 쌍을 순회하는 방법은 유일하다. (즉 도로의 그래프가 트리 형태이다)

도시가 공격당했을 때, 최대한 빠른 시간 내에 이 사실을 수도에 보고해야 한다. 각 도시에 살고 있는 전령들이 이 메시지를 전달한다. 각각의 전령에는 여정을 시작하기 위해 필요한 시간과 일정 속력(킬로미터 당 분 단위)이 있다.

도시에서 출발한 메시지는 수도까지 유일한 가장 짧은 경로를 통해서 전달된다. 처음에는 공격당한 도시의 전령이 메시지를 전달한다. 그 전령이 순회하는 다른 도시에서 전령은 두 가지 선택을 할 수 있다. 수도 방향의 다음 도시로 이동하거나, 그 도시의 전령에게 메시지를 남길 수 있다. 새로운 전령은 위와 같은 방식을 따른다. 종합해보면, 메시지는 수도까지 전달되는 동안 여러 전령을 거칠 수 있다.

이때, 각 도시에서 수도까지 메시지를 전하는데 걸리는 최소 시간을 구하여라.

입력

첫째 줄엔, 몰다비아의 도시의 개수 N이 주어진다.

다음 줄부터 N-1개의 줄에 공백으로 구분된 세 개의 정수 U, V, D가 주어진다. 이는 도시 U와 도시 V 사이에 D 킬로미터의 도로가 있음을 의미한다.

그 아래에, 한 줄에 하나씩 N-1개의 정수 쌍이 주어진다. i번째 쌍인 Si, Vi는 (i+1)번째 도시의 전령을 표현하는 수이다. Si는 여정을 준비하는데 걸리는 시간, Vi는 1km를 가는데 걸리는 시간(분)이다. 수도에는 전령이 없다.

출력

표준 출력에는 N-1개의 정수로 이루어진 하나의 줄을 출력해야 한다. i번째 수는 (i+1)번째 도시에서 수도로 메시지를 보내는데 필요한 최소 시간(분)을 나타낸다.

제한

  • 3 ≤ N ≤ 100,000
  • 0 ≤ Si ≤ 109
  • 1 ≤ Vi ≤ 109
  • 각 도로의 길이는 10,000을 넘지 않는다.

예제 입력 1

5
1 2 20
2 3 12
2 4 1
4 5 3
26 9
1 10
500 2
2 30

예제 출력 1

206 321 542 328
W3sicHJvYmxlbV9pZCI6IjMzMTkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4MDRcdWI4MzlcdWI0ZTQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzYxYlx1YjBhMCBcdWM2MWJcdWIwYTBcdWM1ZDAsIFx1YzU0NFx1Yjk4NFx1YjJlNFx1YzZiNCBcdWJhYjBcdWIyZTRcdWJlNDRcdWM1NDRcdWM3NTggXHVjOWMwXHVjNWVkXHVjNWQwIDFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMCBcdWFjZTBcdWM3MjBcdWQ1NWMgXHViYzg4XHVkNjM4XHVhYzAwIFx1YmQ5OVx1YzVlY1x1YzljNCBOXHVhYzFjXHVjNzU4IFx1YzkxMVx1YzEzOCBcdWIzYzRcdWMyZGNcdWFjMDAgXHVjNzg4XHVjNWM4XHViMmU0LiBcdWJjODhcdWQ2MzggMVx1Yzc3NCBcdWJkOTlcdWM1ZWNcdWM5YzQgXHViM2M0XHVjMmRjXHViMjk0IFx1YzIxOFx1YjNjNFx1Yzc3NFx1YjJlNC4gXHViM2M0XHVjMmRjXHViNGU0XHVjNzQwIE4tMVx1YWMxY1x1Yzc1OCBcdWM1OTFcdWJjMjlcdWQ1YTUgXHViM2M0XHViODVjXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YWMwMSBcdWIzYzRcdWI4NWNcdWIyOTQgXHVkMGFjXHViODVjXHViYmY4XHVkMTMwIFx1YjJlOFx1YzcwNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViM2M0XHVjMmRjXHViOTdjIFx1YjQ1MCBcdWJjODggXHVhYzcwXHVjZTU4XHVjOWMwIFx1YzU0YVx1YWNlMCBcdWIzYzRcdWMyZGNcdWM3NTggXHVjMzBkXHVjNzQ0IFx1YzIxY1x1ZDY4Y1x1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NDAgXHVjNzIwXHVjNzdjXHVkNTU4XHViMmU0LiAoXHVjOTg5IFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWFkZjhcdWI3OThcdWQ1MDRcdWFjMDAgXHVkMmI4XHViOWFjIFx1ZDYxNVx1ZDBkY1x1Yzc3NFx1YjJlNCk8XC9wPlxyXG5cclxuPHA+XHViM2M0XHVjMmRjXHVhYzAwIFx1YWNmNVx1YWNhOVx1YjJmOVx1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1Y2Q1Y1x1YjMwMFx1ZDU1YyBcdWJlNjBcdWI5NzggXHVjMmRjXHVhYzA0IFx1YjBiNFx1YzVkMCBcdWM3NzQgXHVjMGFjXHVjMmU0XHVjNzQ0IFx1YzIxOFx1YjNjNFx1YzVkMCBcdWJjZjRcdWFjZTBcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWFjMDEgXHViM2M0XHVjMmRjXHVjNWQwIFx1YzBiNFx1YWNlMCBcdWM3ODhcdWIyOTQgXHVjODA0XHViODM5XHViNGU0XHVjNzc0IFx1Yzc3NCBcdWJhNTRcdWMyZGNcdWM5YzBcdWI5N2MgXHVjODA0XHViMmVjXHVkNTVjXHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVjODA0XHViODM5XHVjNWQwXHViMjk0IFx1YzVlY1x1YzgxNVx1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWMyZGNcdWFjMDRcdWFjZmMgXHVjNzdjXHVjODE1IFx1YzE4ZFx1YjgyNShcdWQwYWNcdWI4NWNcdWJiZjhcdWQxMzAgXHViMmY5IFx1YmQ4NCBcdWIyZThcdWM3MDQpXHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViM2M0XHVjMmRjXHVjNWQwXHVjMTFjIFx1Y2Q5Y1x1YmMxY1x1ZDU1YyBcdWJhNTRcdWMyZGNcdWM5YzBcdWIyOTQgXHVjMjE4XHViM2M0XHVhZTRjXHVjOWMwIFx1YzcyMFx1Yzc3Y1x1ZDU1YyBcdWFjMDBcdWM3YTUgXHVjOWU3XHVjNzQwIFx1YWNiZFx1Yjg1Y1x1Yjk3YyBcdWQxYjVcdWQ1NzRcdWMxMWMgXHVjODA0XHViMmVjXHViNDFjXHViMmU0LiBcdWNjOThcdWM3NGNcdWM1ZDBcdWIyOTQgXHVhY2Y1XHVhY2E5XHViMmY5XHVkNTVjIFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWM4MDRcdWI4MzlcdWM3NzQgXHViYTU0XHVjMmRjXHVjOWMwXHViOTdjIFx1YzgwNFx1YjJlY1x1ZDU1Y1x1YjJlNC4gXHVhZGY4IFx1YzgwNFx1YjgzOVx1Yzc3NCBcdWMyMWNcdWQ2OGNcdWQ1NThcdWIyOTQgXHViMmU0XHViOTc4IFx1YjNjNFx1YzJkY1x1YzVkMFx1YzExYyBcdWM4MDRcdWI4MzlcdWM3NDAgXHViNDUwIFx1YWMwMFx1YzljMCBcdWMxMjBcdWQwZGRcdWM3NDQgXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzIxOFx1YjNjNCBcdWJjMjlcdWQ1YTVcdWM3NTggXHViMmU0XHVjNzRjIFx1YjNjNFx1YzJkY1x1Yjg1YyBcdWM3NzRcdWIzZDlcdWQ1NThcdWFjNzBcdWIwOTgsIFx1YWRmOCBcdWIzYzRcdWMyZGNcdWM3NTggXHVjODA0XHViODM5XHVjNWQwXHVhYzhjIFx1YmE1NFx1YzJkY1x1YzljMFx1Yjk3YyBcdWIwYThcdWFlMzggXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjMGM4XHViODVjXHVjNmI0IFx1YzgwNFx1YjgzOVx1Yzc0MCBcdWM3MDRcdWM2NDAgXHVhYzE5XHVjNzQwIFx1YmMyOVx1YzJkZFx1Yzc0NCBcdWI1MzBcdWI5NzhcdWIyZTQuIFx1Yzg4NVx1ZDU2OVx1ZDU3NFx1YmNmNFx1YmE3NCwgXHViYTU0XHVjMmRjXHVjOWMwXHViMjk0IFx1YzIxOFx1YjNjNFx1YWU0Y1x1YzljMCBcdWM4MDRcdWIyZWNcdWI0MThcdWIyOTQgXHViM2Q5XHVjNTQ4IFx1YzVlY1x1YjdlYyBcdWM4MDRcdWI4MzlcdWM3NDQgXHVhYzcwXHVjZTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YjU0YywgXHVhYzAxIFx1YjNjNFx1YzJkY1x1YzVkMFx1YzExYyBcdWMyMThcdWIzYzRcdWFlNGNcdWM5YzAgXHViYTU0XHVjMmRjXHVjOWMwXHViOTdjIFx1YzgwNFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjZDVjXHVjMThjIFx1YzJkY1x1YWMwNFx1Yzc0NCBcdWFkNmNcdWQ1NThcdWM1ZWNcdWI3N2MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQ0LCBcdWJhYjBcdWIyZTRcdWJlNDRcdWM1NDRcdWM3NTggXHViM2M0XHVjMmRjXHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIFx1YzkwNFx1YmQ4MFx1ZDEzMCBOLTFcdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MWMgXHVjMTM4IFx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggVSwgViwgRFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjI5NCBcdWIzYzRcdWMyZGMgVVx1YzY0MCBcdWIzYzRcdWMyZGMgViBcdWMwYWNcdWM3NzRcdWM1ZDAgRCBcdWQwYWNcdWI4NWNcdWJiZjhcdWQxMzBcdWM3NTggXHViM2M0XHViODVjXHVhYzAwIFx1Yzc4OFx1Yzc0Y1x1Yzc0NCBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWRmOCBcdWM1NDRcdWI3OThcdWM1ZDAsIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IE4tMVx1YWMxY1x1Yzc1OCBcdWM4MTVcdWMyMTggXHVjMzBkXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gaVx1YmM4OFx1YzlmOCBcdWMzMGRcdWM3NzggUzxzdWI+aTxcL3N1Yj4sIFY8c3ViPmk8XC9zdWI+XHViMjk0IChpKzEpXHViYzg4XHVjOWY4IFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWM4MDRcdWI4MzlcdWM3NDQgXHVkNDVjXHVkNjA0XHVkNTU4XHViMjk0IFx1YzIxOFx1Yzc3NFx1YjJlNC4gUzxzdWI+aTxcL3N1Yj5cdWIyOTQgXHVjNWVjXHVjODE1XHVjNzQ0IFx1YzkwMFx1YmU0NFx1ZDU1OFx1YjI5NFx1YjM3MCBcdWFjNzhcdWI5YWNcdWIyOTQgXHVjMmRjXHVhYzA0LCBWPHN1Yj5pPFwvc3ViPlx1YjI5NCAxa21cdWI5N2MgXHVhYzAwXHViMjk0XHViMzcwIFx1YWM3OFx1YjlhY1x1YjI5NCBcdWMyZGNcdWFjMDQoXHViZDg0KVx1Yzc3NFx1YjJlNC4gXHVjMjE4XHViM2M0XHVjNWQwXHViMjk0IFx1YzgwNFx1YjgzOVx1Yzc3NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVkNDVjXHVjOTAwIFx1Y2Q5Y1x1YjgyNVx1YzVkMFx1YjI5NCBOLTFcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWQ1NThcdWIwOThcdWM3NTggXHVjOTA0XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIGlcdWJjODhcdWM5ZjggXHVjMjE4XHViMjk0IChpKzEpXHViYzg4XHVjOWY4IFx1YjNjNFx1YzJkY1x1YzVkMFx1YzExYyBcdWMyMThcdWIzYzRcdWI4NWMgXHViYTU0XHVjMmRjXHVjOWMwXHViOTdjIFx1YmNmNFx1YjBiNFx1YjI5NFx1YjM3MCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjZDVjXHVjMThjIFx1YzJkY1x1YWMwNChcdWJkODQpXHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+MyAmbGU7IE4gJmxlOyAxMDAsMDAwPFwvbGk+XHJcblx0PGxpPjAgJmxlOyBTPHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD45PFwvc3VwPjxcL2xpPlxyXG5cdDxsaT4xICZsZTsgVjxzdWI+aTxcL3N1Yj4gJmxlOyAxMDxzdXA+OTxcL3N1cD48XC9saT5cclxuXHQ8bGk+XHVhYzAxIFx1YjNjNFx1Yjg1Y1x1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgMTAsMDAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG4ifSx7InByb2JsZW1faWQiOiIzMzE5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiaGFyYmluZ2VycyIsImRlc2NyaXB0aW9uIjoiPHA+T25jZSB1cG9uIGEgdGltZSwgdGhlcmUgd2VyZSBOIG1lZGlldmFsIHRvd25zIGluIHRoZSBiZWF1dGlmdWwgTW9sZGF2aWFuIHRlcnJpdG9yeSwgdW5pcXVlbHkgbnVtYmVyZWQgZnJvbSAxIHRocm91Z2ggTi4gVGhlIHRvd24gbnVtYmVyZWQgd2l0aCAxIHdhcyB0aGUgY2FwaXRhbCBjaXR5LiBUaGUgdG93bnMgd2VyZSBjb25uZWN0ZWQgYnkgTi0xIGJpZGlyZWN0aW9uYWwgcm9hZHMsIGVhY2ggcm9hZCBoYXZpbmcgYSBsZW5ndGggZXhwcmVzc2VkIGluIGtpbG9tZXRlcnMuIFRoZXJlIHdhcyBhIHVuaXF1ZSB3YXkgdG8gdHJhdmVsIGJldHdlZW4gYW55IHBhaXIgb2YgdG93bnMgd2l0aG91dCBnb2luZyB0aHJvdWdoIGEgdG93biB0d2ljZSAoaS5lLiB0aGUgZ3JhcGggb2Ygcm9hZHMgd2FzIGEgdHJlZSkuPFwvcD5cclxuXHJcbjxwPldoZW4gYSB0b3duIHdhcyBhdHRhY2tlZCwgdGhlIHNpdHVhdGlvbiBoYWQgdG8gYmUgcmVwb3J0ZWQgYXMgc29vbiBhcyBwb3NzaWJsZSB0byB0aGUgY2FwaXRhbC4gVGhlIG1lc3NhZ2Ugd2FzIGNhcnJpZWQgYnkgaGFyYmluZ2Vycywgb25lIG9mIHdoaWNoIHJlc2lkZWQgaW4gZWFjaCB0b3duLiBFYWNoIGhhcmJpbmdlciB3YXMgY2hhcmFjdGVyaXplZCBieSB0aGUgYW1vdW50IG9mIHRpbWUgcmVxdWlyZWQgdG8gc3RhcnQgdGhlIGpvdXJuZXkgYW5kIGJ5IGhpcyBjb25zdGFudCBzcGVlZCAoZXhwcmVzc2VkIGluIG1pbnV0ZXMgcGVyIGtpbG9tZXRlcikgYWZ0ZXIgZGVwYXJ0dXJlLjxcL3A+XHJcblxyXG48cD5UaGUgbWVzc2FnZSBmcm9tIGEgdG93biB3YXMgYWx3YXlzIGNhcnJpZWQgb24gdGhlIHVuaXF1ZSBzaG9ydGVzdCBwYXRoIHRvIHRoZSBjYXBpdGFsLiBJbml0aWFsbHksIHRoZSBoYXJiaW5nZXIgZnJvbSB0aGUgYXR0YWNrZWQgdG93biBjYXJyaWVkIHRoZSBtZXNzYWdlLiBJbiBlYWNoIHRvd24gdGhhdCBoZSB0cmF2ZXJzZWQsIGEgaGFyYmluZ2VyIGhhZCB0d28gb3B0aW9uczogZWl0aGVyIGdvIHRvIHRoZSBuZXh0IHRvd24gdG93YXJkcyB0aGUgY2FwaXRhbCwgb3IgbGVhdmUgdGhlIG1lc3NhZ2UgdG8gdGhlIGhhcmJpbmdlciBmcm9tIHRoaXMgdG93bi4gVGhlIG5ldyBoYXJiaW5nZXIgYXBwbGllZCB0aGUgc2FtZSBhbGdvcml0aG0gYXMgYWJvdmUuIE92ZXJhbGwsIGEgbWVzc2FnZSBjb3VsZCBiZSBjYXJyaWVkIGJ5IGFueSBudW1iZXIgb2YgaGFyYmluZ2VycyBiZWZvcmUgYXJyaXZpbmcgaW4gdGhlIGNhcGl0YWwuPFwvcD5cclxuXHJcbjxwPllvdXIgdGFzayBpcyB0byBmaW5kLCBmb3IgZWFjaCB0b3duLCB0aGUgbWluaW11bSB0aW1lIHJlcXVpcmVkIHRvIHNlbmQgYSBtZXNzYWdlIGZyb20gdGhhdCB0b3duIHRvIHRoZSBjYXBpdGFsLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIHN0YW5kYXJkIGlucHV0IGNvbnRhaW5zIG9uZSBpbnRlZ2VyIE4sIHRoZSBudW1iZXIgb2YgdG93bnMgaW4gTW9sZGF2aWEuIEVhY2ggb2YgdGhlIGZvbGxvd2luZyBOLTEgbGluZXMgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgdSB2IGQsIHNlcGFyYXRlZCBieSBvbmUgc3BhY2UsIGRlc2NyaWJpbmcgYSByb2FkIG9mIGxlbmd0aCBkIGtpbG9tZXRlcnMgYmV0d2VlbiB0b3ducyBudW1iZXJlZCB3aXRoIHUgYW5kIHYuIFN1YnNlcXVlbnRseSwgTi0xIHBhaXJzIG9mIGludGVnZXJzIGZvbGxvdywgb25lIHBlciBsaW5lLiBUaGUgaXRoIHBhaXIsIFM8c3ViPmk8XC9zdWI+IFY8c3ViPmk8XC9zdWI+LCBkZXNjcmliZXMgdGhlIGNoYXJhY3RlcmlzdGljcyBvZiB0aGUgaGFyYmluZ2VyIGluIHRoZSAoaSsxKXRoIHRvd246IFM8c3ViPmk8XC9zdWI+IGlzIHRoZSBudW1iZXIgb2YgbWludXRlcyB0byBwcmVwYXJlIGZvciB0aGUgam91cm5leSwgYW5kIFY8c3ViPmk8XC9zdWI+IGlzIHRoZSBudW1iZXIgb2YgbWludXRlcyBuZWVkZWQgdG8gdHJhdmVsIG9uZSBraWxvbWV0ZXIuIFRoZXJlIGlzIG5vIGhhcmJpbmdlciBpbiB0aGUgY2FwaXRhbC4mbmJzcDs8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4zICZsZTsgTiAmbGU7IDEwMCAwMDA8XC9saT5cclxuXHQ8bGk+MCAmbGU7IFM8c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjk8XC9zdXA+PFwvbGk+XHJcblx0PGxpPjEgJmxlOyBWPHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD45PFwvc3VwPjxcL2xpPlxyXG5cdDxsaT5UaGUgbGVuZ3RoIG9mIGVhY2ggcm9hZCB3aWxsIG5vdCBleGNlZWQgMTAgMDAwPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgc3RhbmRhcmQgb3V0cHV0IHNob3VsZCBjb25zaXN0IG9mIGV4YWN0bHkgb25lIGxpbmUgY29udGFpbmluZyBOLTEgaW50ZWdlcnMuIFRoZSBpdGggbnVtYmVyIHJlcHJlc2VudHMgdGhlIG1pbmltdW0gdGltZSwgaW4gbWludXRlcywgcmVxdWlyZWQgdG8gc2VuZCBhIG1lc3NhZ2UgZnJvbSB0aGUgKGkrMSl0aCB0b3duIHRvIHRoZSBjYXBpdGFsLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

Olympiad > Central European Olympiad in Informatics > CEOI 2009 > Day 1 2번