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

문제

모범생 현수는 코딩하는 시간을 늘리기 위해 타임 머신을 구매 했다. 현수는 정상적으로 문제를 코딩하거나 (타임 머신을 사용하지 않고), 과거의 임의의 지점으로 시간여행 할 수 있다.  미래로 시간 여행 할 수 없으며, 과거로 가면 새로운 미래가 진행된다.

현수는 자유롭게 문제를 풀거나 과거로 돌아가면서 자신이 푼 문제 목록을 기록한다. 과거로 돌아가면 과거 이전까지 풀었던 문제 목록만 남는다.

현수는  기록 되어 있는 문제 목록 중 가장 최근에 푼 문제 번호를 알고 싶다. (가장 최근에 푼 문제가 없다면 -1을 출력)

매 쿼리마다 문제 목록에 기록되어 있는 가장 최근에 푼 문제를 출력하는 프로그램을 작성하시오.

현수는 개인의 타임라인 관점에서 연속적인 업데이트를 나타내는  N (1 <= N <= 80,000) 개의 쿼리 Qi(1...N) 를 제공한다.

각 쿼리는 한 줄의 입력이다. 각 줄은 하나의 문자 c ( 'a', 's', 't' 중 하나)로 시작한다. c가 'a'또는 't' 이면 c 다음에 공백과 정수 K가 주어진다. (1 <= K <= 1,000,000)

c가 'a' 이면 현수는 문제 번호가 K인 문제를 풀고 문제 목록에 기록 한다.

c가 's' 이면 현수는 가장 최근에 작성한 문제 목록을 삭제한다.

c가 't'이면, 현수는 K 번째 쿼리 직전까지 시간을 거슬러 올라 간다. 즉, 현수는 K-1번째 쿼리와 K번째 쿼리 사이로 시간 여행한다. (입력을 위해 예제 입력 참조). K 쿼리  바로 전에 있던 푼 문제 목록으로 되돌아 간다.

이해를 돕기 위해 아래에 푼 문제 목록과 12개의 쿼리, 각 쿼리에 대한 출력결과가 주어진다.  

Q#   쿼리     문제목록      출력         참조
 1   a 5  -> [5]         => 5        5번 문제를 목록에 기록
 2   a 3  -> [5,3]       => 3        3번 문제를  목록에 기록
 3   a 7  -> [5,3,7]     => 7        7번 문제를 목록에 기록
 4   s    -> [5,3]       => 3        가장 최근 기록한 7를 목록에서 삭제
 5   t 2  -> [5]         => 5        2번째 쿼리 직전으로 되돌아감
 6   a 2  -> [5,2]       => 2        2번 문제를 목록에 기록
 7   t 4  -> [5,3,7]     => 7        4번째 쿼리 직전으로 되돌아감
 8   a 4  -> [5,3,7,4]   => 4        4번 문제를 목록에 기록
 9   s    -> [5,3,7]     => 7        가장 최근 기록한 4를 목록에서 삭제
10   t 7  -> [5,2]       => 2        7번째 쿼리 직전으로 되돌아감
11   s    -> [5]         => 5        가장 최근 기록한 2를 목록에서 삭제
12   s    -> []          => -1       가장 최근 기록한 5를 목록에서 삭제

입력

첫 번째 줄 : 하나의 정수 N

두 번째 줄 부터 N+1번째 줄까지: 쿼리 Qi 

출력

1부터 N번째 줄 : Qi 처리 후 목록에 기록 되어 있는 가장 최근에 푼 문제를 출력하시오 (가장 최근에 푼 문제가 없으면 -1).

예제 입력 1

12
a 5
a 3
a 7
s
t 2
a 2
t 4
a 4
s
t 7
s
s

예제 출력 1

5
3
7
3
5
2
7
4
7
2
5
-1
W3sicHJvYmxlbV9pZCI6IjYwNTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyZGNcdWFjMDQgXHVjNWVjXHVkNTg5IiwiZGVzY3JpcHRpb24iOiI8cD5cdWJhYThcdWJjOTRcdWMwZGQgXHVkNjA0XHVjMjE4XHViMjk0IFx1Y2Y1NFx1YjUyOVx1ZDU1OFx1YjI5NCBcdWMyZGNcdWFjMDRcdWM3NDQmbmJzcDtcdWIyOThcdWI5YWNcdWFlMzAgXHVjNzA0XHVkNTc0Jm5ic3A7XHVkMGMwXHVjNzg0IFx1YmEzOFx1YzJlMFx1Yzc0NCBcdWFkNmNcdWI5ZTQgXHVkNTg4XHViMmU0LiZuYnNwO1x1ZDYwNFx1YzIxOFx1YjI5NCBcdWM4MTVcdWMwYzFcdWM4MDFcdWM3M2NcdWI4NWMgXHViYjM4XHVjODFjXHViOTdjIFx1Y2Y1NFx1YjUyOVx1ZDU1OFx1YWM3MFx1YjA5OCAoXHVkMGMwXHVjNzg0IFx1YmEzOFx1YzJlMFx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NThcdWM5YzAgXHVjNTRhXHVhY2UwKSwgXHVhY2ZjXHVhYzcwXHVjNzU4IFx1Yzc4NFx1Yzc1OFx1Yzc1OCBcdWM5YzBcdWM4MTBcdWM3M2NcdWI4NWMgXHVjMmRjXHVhYzA0XHVjNWVjXHVkNTg5IFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LiZuYnNwOyBcdWJiZjhcdWI3OThcdWI4NWMgXHVjMmRjXHVhYzA0IFx1YzVlY1x1ZDU4OSBcdWQ1NjAgXHVjMjE4IFx1YzVjNlx1YzczY1x1YmE3MCwgXHVhY2ZjXHVhYzcwXHViODVjIFx1YWMwMFx1YmE3NCBcdWMwYzhcdWI4NWNcdWM2YjQgXHViYmY4XHViNzk4XHVhYzAwIFx1YzljNFx1ZDU4OVx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkNjA0XHVjMjE4XHViMjk0IFx1Yzc5MFx1YzcyMFx1Yjg2ZFx1YWM4YyBcdWJiMzhcdWM4MWNcdWI5N2MmbmJzcDtcdWQ0ODBcdWFjNzBcdWIwOTggXHVhY2ZjXHVhYzcwXHViODVjIFx1YjNjY1x1YzU0NFx1YWMwMFx1YmE3NFx1YzExYyBcdWM3OTBcdWMyZTBcdWM3NzQgXHVkNDdjIFx1YmIzOFx1YzgxYyBcdWJhYTlcdWI4NWRcdWM3NDQgXHVhZTMwXHViODVkXHVkNTVjXHViMmU0LiBcdWFjZmNcdWFjNzBcdWI4NWMgXHViM2NjXHVjNTQ0XHVhYzAwXHViYTc0IFx1YWNmY1x1YWM3MCBcdWM3NzRcdWM4MDRcdWFlNGNcdWM5YzAgXHVkNDgwXHVjNWM4XHViMzU4IFx1YmIzOFx1YzgxYyBcdWJhYTlcdWI4NWRcdWI5Y2MgXHViMGE4XHViMjk0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ2MDRcdWMyMThcdWIyOTQmbmJzcDsgXHVhZTMwXHViODVkIFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHViYjM4XHVjODFjIFx1YmFhOVx1Yjg1ZCBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1Y2Q1Y1x1YWRmY1x1YzVkMCBcdWQ0N2MgXHViYjM4XHVjODFjIFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWM1NGNcdWFjZTAgXHVjMmY2XHViMmU0LiAoXHVhYzAwXHVjN2E1IFx1Y2Q1Y1x1YWRmY1x1YzVkMCBcdWQ0N2MgXHViYjM4XHVjODFjXHVhYzAwIFx1YzVjNlx1YjJlNFx1YmE3NCAtMVx1Yzc0NCBcdWNkOWNcdWI4MjUpPFwvcD5cclxuXHJcbjxwPlx1YjllNCBcdWNmZmNcdWI5YWNcdWI5YzhcdWIyZTQgXHViYjM4XHVjODFjIFx1YmFhOVx1Yjg1ZFx1YzVkMCZuYnNwO1x1YWUzMFx1Yjg1ZFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyOTQgXHVhYzAwXHVjN2E1IFx1Y2Q1Y1x1YWRmY1x1YzVkMCBcdWQ0N2MgXHViYjM4XHVjODFjXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcblxyXG48cD5cdWQ2MDRcdWMyMThcdWIyOTQgXHVhYzFjXHVjNzc4XHVjNzU4IFx1ZDBjMFx1Yzc4NFx1Yjc3Y1x1Yzc3OCBcdWFkMDBcdWM4MTBcdWM1ZDBcdWMxMWMmbmJzcDtcdWM1ZjBcdWMxOGRcdWM4MDFcdWM3NzggXHVjNWM1XHViMzcwXHVjNzc0XHVkMmI4XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCAmbmJzcDtOICgxICZsdDs9IE4gJmx0Oz0gODAsMDAwKSBcdWFjMWNcdWM3NTggXHVjZmZjXHViOWFjIFE8c3ViPmk8XC9zdWI+KDEuLi5OKSBcdWI5N2MgXHVjODFjXHVhY2Y1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVjZmZjXHViOWFjXHViMjk0IFx1ZDU1YyBcdWM5MDRcdWM3NTggXHVjNzg1XHViODI1XHVjNzc0XHViMmU0LiBcdWFjMDEgXHVjOTA0XHVjNzQwIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWJiMzhcdWM3OTAgYyAoICYjMzk7YSYjMzk7LCAmIzM5O3MmIzM5OywgJiMzOTt0JiMzOTsgXHVjOTExIFx1ZDU1OFx1YjA5OClcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTVjXHViMmU0LiBjXHVhYzAwICYjMzk7YSYjMzk7XHViNjEwXHViMjk0ICYjMzk7dCYjMzk7IFx1Yzc3NFx1YmE3NCBjIFx1YjJlNFx1Yzc0Y1x1YzVkMCBcdWFjZjVcdWJjMzFcdWFjZmMgXHVjODE1XHVjMjE4IEtcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiZuYnNwOygxICZsdDs9IEsgJmx0Oz0gMSwwMDAsMDAwKTxcL3A+XHJcblxyXG48cD5jXHVhYzAwICYjMzk7YSYjMzk7IFx1Yzc3NFx1YmE3NCBcdWQ2MDRcdWMyMThcdWIyOTQgXHViYjM4XHVjODFjIFx1YmM4OFx1ZDYzOFx1YWMwMCBLXHVjNzc4IFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWQ0ODBcdWFjZTAgXHViYjM4XHVjODFjIFx1YmFhOVx1Yjg1ZFx1YzVkMCBcdWFlMzBcdWI4NWQgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5jXHVhYzAwICYjMzk7cyYjMzk7IFx1Yzc3NFx1YmE3NCBcdWQ2MDRcdWMyMThcdWIyOTQgXHVhYzAwXHVjN2E1IFx1Y2Q1Y1x1YWRmY1x1YzVkMCBcdWM3OTFcdWMxMzFcdWQ1NWMgXHViYjM4XHVjODFjIFx1YmFhOVx1Yjg1ZFx1Yzc0NCBcdWMwYWRcdWM4MWNcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPmNcdWFjMDAgJiMzOTt0JiMzOTtcdWM3NzRcdWJhNzQsIFx1ZDYwNFx1YzIxOFx1YjI5NCBLIFx1YmM4OFx1YzlmOCZuYnNwO1x1Y2ZmY1x1YjlhYyBcdWM5YzFcdWM4MDRcdWFlNGNcdWM5YzAgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YWM3MFx1YzJhY1x1YjdlYyBcdWM2MmNcdWI3N2MgXHVhYzA0XHViMmU0LiBcdWM5ODksIFx1ZDYwNFx1YzIxOFx1YjI5NCBLLTFcdWJjODhcdWM5ZjggXHVjZmZjXHViOWFjXHVjNjQwIEtcdWJjODhcdWM5ZjggXHVjZmZjXHViOWFjIFx1YzBhY1x1Yzc3NFx1Yjg1YyBcdWMyZGNcdWFjMDQgXHVjNWVjXHVkNTg5XHVkNTVjXHViMmU0LiAoXHVjNzg1XHViODI1XHVjNzQ0IFx1YzcwNFx1ZDU3NCBcdWM2MDhcdWM4MWMgXHVjNzg1XHViODI1IFx1Y2MzOFx1Yzg3MCkuIEsgXHVjZmZjXHViOWFjJm5ic3A7IFx1YmMxNFx1Yjg1YyBcdWM4MDRcdWM1ZDAgXHVjNzg4XHViMzU4IFx1ZDQ3YyBcdWJiMzhcdWM4MWMgXHViYWE5XHViODVkXHVjNzNjXHViODVjIFx1YjQxOFx1YjNjY1x1YzU0NCBcdWFjMDRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1ZDU3NFx1Yjk3YyBcdWIzZDVcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YzU0NFx1Yjc5OFx1YzVkMCZuYnNwO1x1ZDQ3YyBcdWJiMzhcdWM4MWMgXHViYWE5XHViODVkXHVhY2ZjIDEyXHVhYzFjXHVjNzU4Jm5ic3A7XHVjZmZjXHViOWFjLCZuYnNwO1x1YWMwMSBcdWNmZmNcdWI5YWNcdWM1ZDAgXHViMzAwXHVkNTVjJm5ic3A7XHVjZDljXHViODI1XHVhY2IwXHVhY2ZjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsmbmJzcDs8XC9wPlxyXG5cclxuPHByZT5cclxuUSMgICBcdWNmZmNcdWI5YWMgICAgIFx1YmIzOFx1YzgxY1x1YmFhOVx1Yjg1ZCAgICAgIFx1Y2Q5Y1x1YjgyNSAgICAgICAgIFx1Y2MzOFx1Yzg3MFxyXG4gMSAgIGEgNSAgLSZndDsgWzVdICAgICAgICAgPSZndDsgNSAgICAgICAgNVx1YmM4OCBcdWJiMzhcdWM4MWNcdWI5N2MgXHViYWE5XHViODVkXHVjNWQwIFx1YWUzMFx1Yjg1ZFxyXG4gMiAgIGEgMyAgLSZndDsgWzUsM10gICAgICAgPSZndDsgMyAgICAgICAgM1x1YmM4OCBcdWJiMzhcdWM4MWNcdWI5N2MgIFx1YmFhOVx1Yjg1ZFx1YzVkMCBcdWFlMzBcdWI4NWRcclxuIDMgICBhIDcgIC0mZ3Q7IFs1LDMsN10gICAgID0mZ3Q7IDcgICAgICAgIDdcdWJjODggXHViYjM4XHVjODFjXHViOTdjIFx1YmFhOVx1Yjg1ZFx1YzVkMCBcdWFlMzBcdWI4NWRcclxuIDQgICBzICAgIC0mZ3Q7IFs1LDNdICAgICAgID0mZ3Q7IDMgICAgICAgIFx1YWMwMFx1YzdhNSBcdWNkNWNcdWFkZmMgXHVhZTMwXHViODVkXHVkNTVjIDdcdWI5N2MgXHViYWE5XHViODVkXHVjNWQwXHVjMTFjIFx1YzBhZFx1YzgxY1xyXG4gNSAgIHQgMiAgLSZndDsgWzVdICAgICAgICAgPSZndDsgNSAgICAgICAgMlx1YmM4OFx1YzlmOCBcdWNmZmNcdWI5YWMgXHVjOWMxXHVjODA0XHVjNzNjXHViODVjIFx1YjQxOFx1YjNjY1x1YzU0NFx1YWMxMFxyXG4gNiAgIGEgMiAgLSZndDsgWzUsMl0gICAgICAgPSZndDsgMiAgICAgICAgMlx1YmM4OCBcdWJiMzhcdWM4MWNcdWI5N2MgXHViYWE5XHViODVkXHVjNWQwIFx1YWUzMFx1Yjg1ZFxyXG4gNyAgIHQgNCAgLSZndDsgWzUsMyw3XSAgICAgPSZndDsgNyAgICAgICAgNFx1YmM4OFx1YzlmOCBcdWNmZmNcdWI5YWMgXHVjOWMxXHVjODA0XHVjNzNjXHViODVjIFx1YjQxOFx1YjNjY1x1YzU0NFx1YWMxMFxyXG4gOCAgIGEgNCAgLSZndDsgWzUsMyw3LDRdICAgPSZndDsgNCAgICAgICAgNFx1YmM4OCBcdWJiMzhcdWM4MWNcdWI5N2MgXHViYWE5XHViODVkXHVjNWQwIFx1YWUzMFx1Yjg1ZFxyXG4gOSAgIHMgICAgLSZndDsgWzUsMyw3XSAgICAgPSZndDsgNyAgICAgICAgXHVhYzAwXHVjN2E1IFx1Y2Q1Y1x1YWRmYyBcdWFlMzBcdWI4NWRcdWQ1NWMgNFx1Yjk3YyBcdWJhYTlcdWI4NWRcdWM1ZDBcdWMxMWMgXHVjMGFkXHVjODFjXHJcbjEwICAgdCA3ICAtJmd0OyBbNSwyXSAgICAgICA9Jmd0OyAyICAgICAgICA3XHViYzg4XHVjOWY4IFx1Y2ZmY1x1YjlhYyBcdWM5YzFcdWM4MDRcdWM3M2NcdWI4NWMgXHViNDE4XHViM2NjXHVjNTQ0XHVhYzEwXHJcbjExICAgcyAgICAtJmd0OyBbNV0gICAgICAgICA9Jmd0OyA1ICAgICAgICBcdWFjMDBcdWM3YTUgXHVjZDVjXHVhZGZjIFx1YWUzMFx1Yjg1ZFx1ZDU1YyAyXHViOTdjIFx1YmFhOVx1Yjg1ZFx1YzVkMFx1YzExYyBcdWMwYWRcdWM4MWNcclxuMTIgICBzICAgIC0mZ3Q7IFtdICAgICAgICAgID0mZ3Q7IC0xICAgICAgIFx1YWMwMFx1YzdhNSBcdWNkNWNcdWFkZmMgXHVhZTMwXHViODVkXHVkNTVjIDVcdWI5N2MgXHViYWE5XHViODVkXHVjNWQwXHVjMTFjIFx1YzBhZFx1YzgxYzxcL3ByZT5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNCA6IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWM4MTVcdWMyMTggTjxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNCBcdWJkODBcdWQxMzAgTisxXHViYzg4XHVjOWY4IFx1YzkwNFx1YWU0Y1x1YzljMDogXHVjZmZjXHViOWFjIFE8c3ViPmk8XC9zdWI+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+MVx1YmQ4MFx1ZDEzMCBOXHViYzg4XHVjOWY4IFx1YzkwNCA6IFE8c3ViPmk8XC9zdWI+IFx1Y2M5OFx1YjlhYyBcdWQ2YzQgXHViYWE5XHViODVkXHVjNWQwIFx1YWUzMFx1Yjg1ZCBcdWI0MThcdWM1YjQgXHVjNzg4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWNkNWNcdWFkZmNcdWM1ZDAgXHVkNDdjIFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWMyZGNcdWM2MjQgKFx1YWMwMFx1YzdhNSBcdWNkNWNcdWFkZmNcdWM1ZDAgXHVkNDdjIFx1YmIzOFx1YzgxY1x1YWMwMCBcdWM1YzZcdWM3M2NcdWJhNzQgLTEpLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjYwNTEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJUaW1lIFRyYXZlbCIsImRlc2NyaXB0aW9uIjoiPHA+RmFybWVyIEpvaG4gaGFzIHB1cmNoYXNlZCBhbiBBY21lIFRpbWUgTWFjaGluZS4gSGUgY2FuIG5vdyB0cmF2ZWwgZm9yd2FyZCBpbiB0aW1lIG5vcm1hbGx5ICh3aXRob3V0IHVzaW5nIHRoZSBtYWNoaW5lKSBvciBlbHNlIGp1bXAgYmFjayB0byBhbiBhcmJpdHJhcnkgcG9pbnQgaW4gdGhlIHBhc3QsIGF0IHdoaWNoIHBvaW50IHRpbWUgd2lsbCBzdGFydCB0byBnbyBmb3J3YXJkIGFnYWluLCBidXQgcG90ZW50aWFsbHkgd2l0aCBldmVudHMgdW5mb2xkaW5nIGluIGEgbmV3LCBkaWZmZXJlbnQgd2F5LiBGSiBjYW4gbmV2ZXIgdHJhdmVsIGZvcndhcmQgaW4gdGltZSBpbiBoaXMgdGltZSBtYWNoaW5lLjxcL3A+XHJcblxyXG48cD5GSiB3YW50cyB0byByYWlzZSB0aGUgYmVzdCBwb3NzaWJsZSBjb3cgaGVyZCwgc28gaGUgaXMgZ29pbmcgdG8gdHJ5IHNldmVyYWwgZGlmZmVyZW50IGlkZWFzLCBrZWVwaW5nIHRyYWNrIG9mIHZhcmlvdXMgc3RhdGlzdGljcyBvZiBoaXMgY293IGhlcmQgdGhyb3VnaCBkaWZmZXJlbnQgcG9zc2libGUgdGltZSBhbmQgZXZlbnQgcGF0aHMuPFwvcD5cclxuXHJcbjxwPk9uZSBzdGF0aXN0aWMgRkogY2FyZXMgYWJvdXQgaXMgdGhlIElEIG51bWJlciBvZiB0aGUgY293IGhlIGhhcyBoYWQgZm9yIHRoZSBzaG9ydGVzdCBwZXJpb2Qgb2YgdGltZS4gUGxlYXNlIGhlbHAgaGltIG91dCBieSB3cml0aW5nIGEgcHJvZ3JhbSB0byBrZWVwIHRyYWNrIG9mIGhpcyBoZXJkIGFuZCwgYWZ0ZXIgZWFjaCBjb21tYW5kLCByZXBvcnRpbmcgdGhlIElEIG9mIHRoZSBtb3N0IHJlY2VudGx5IGFjcXVpcmVkIGNvdyBvZiB0aGUgY293cyBoZSBvd25zIChvciAtMSBpZiBoZSBoYXMgbm8gY293cykuPFwvcD5cclxuXHJcbjxwPkZKIGhhcyBhIHNldCBvZiBOICgxICZsdDs9IE4gJmx0Oz0gODAsMDAwKSBxdWVyaWVzIFFfaSwgY29udmVuaWVudGx5IG51bWJlcmVkIDEuLk4sIHdoaWNoIHJlcHJlc2VudCBjb25zZWN1dGl2ZSB1cGRhdGVzIGZyb20gdGhlIHBvaW50IG9mIHZpZXcgb2YgRkomIzM5O3MgcGVyc29uYWwgdGltZWxpbmUuPFwvcD5cclxuXHJcbjxwPkVhY2ggcXVlcnkgaXMgYSBzaW5nbGUgbGluZSBvZiBpbnB1dC4gVGhlIGxpbmUgYmVnaW5zIHdpdGggYSBzaW5nbGUgY2hhcmFjdGVyIGMgKG9uZSBvZiAmIzM5O2EmIzM5OywgJiMzOTtzJiMzOTssIG9yICYjMzk7dCYjMzk7KS4gSWYgYyA9ICYjMzk7YSYjMzk7IG9yIGMgPSAmIzM5O3QmIzM5OywgdGhlbiBjIGlzIGZvbGxvd2VkIGJ5IGEgc3BhY2UgYW5kIGFuIGludGVnZXIgSyAoMSAmbHQ7PSBLICZsdDs9IDEsMDAwLDAwMCkuPFwvcD5cclxuXHJcbjxwPklmIGMgPSAmIzM5O2EmIzM5OywgdGhlbiBGSiBhY3F1aXJlcyBhIGNvdyB3aXRoIElEIEs7IGFkZCB0aGUgY293IHRvIHRoZSBoZXJkLjxcL3A+XHJcblxyXG48cD5JZiBjID0gJiMzOTtzJiMzOTssIHRoZW4gRkogc29sZCBoaXMgbW9zdCByZWNlbnRseSBhY3F1aXJlZCBjb3cgKGl0IGlzIGd1YXJhbnRlZWQgdGhhdCBGSiB3aWxsIGhhdmUgYXQgbGVhc3Qgb25lIGNvdyB3aGVuZXZlciB0aGlzIHR5cGUgb2YgcXVlcnkgYXBwZWFycyk7IHJlbW92ZSB0aGUgY293IGZyb20gdGhlIGhlcmQuPFwvcD5cclxuXHJcbjxwPklmIGMgPSAmIzM5O3QmIzM5OywgdGhlbiBGSiB0cmF2ZWxlZCBiYWNrIGluIHRpbWUgdG8ganVzdCBiZWZvcmUgdGhlIEt0aCBxdWVyeS4gTm90ZSB0aGF0IHRoaXMgbWVhbnMgdGhhdCBGSiBjYW4gcG90ZW50aWFsbHkgdHJhdmVsIGJldHdlZW4gcGFyYWxsZWwgdGltZSBwYXRocyAoc2VlIHNhbXBsZSBpbnB1dCBmb3IgY2xhcmlmaWNhdGlvbikuIFJldmVydCB0byB0aGUgaGVyZCB0aGF0IHdhcyBwcmVzZW50IGp1c3QgYmVmb3JlIHF1ZXJ5IEsuPFwvcD5cclxuXHJcbjxwPkJ5IHdheSBvZiBleGFtcGxlLCBjb25zaWRlciBhIHNlcmllcyBvZiAxMiBxdWVyaWVzLCBzaG93biBiZWxvdyBhbG9uZyB3aXRoIHRoZSBjb3cgbmFtZSBsaXN0IGFuZCB0aGUgcmVzdWx0aW5nIG91dHB1dCBmb3IgZWFjaCBxdWVyeS48XC9wPlxyXG5cclxuPHByZT5cclxuICAgIFEjICAgUXVlcnkgICBPd25lZCBDb3dzICAgIE91dHB1dCAgICAgIENvbW1lbnRzXHJcbiAgICAgMSAgIGEgNSAgLSZndDsgWzVdICAgICAgICA9Jmd0OyA1ICAgICAgICBBZGQgYSBuZXcgY293IHdpdGggSUQgNVxyXG4gICAgIDIgICBhIDMgIC0mZ3Q7IFs1LDNdICAgICAgPSZndDsgMyAgICAgICAgQWRkIGEgbmV3IGNvdyB3aXRoIElEIDNcclxuICAgICAzICAgYSA3ICAtJmd0OyBbNSwzLDddICAgID0mZ3Q7IDcgICAgICAgIEFkZCBhIG5ldyBjb3cgd2l0aCBJRCA3XHJcbiAgICAgNCAgIHMgICAgLSZndDsgWzUsM10gICAgICA9Jmd0OyAzICAgICAgICBTZWxsIHJlY2VudCBjb3cgN1xyXG4gICAgIDUgICB0IDIgIC0mZ3Q7IFs1XSAgICAgICAgPSZndDsgNSAgICAgICAgUmV2ZXJ0IHRpbWUgdG8gYmVmb3JlIHF1ZXJ5IDJcclxuICAgICA2ICAgYSAyICAtJmd0OyBbNSwyXSAgICAgID0mZ3Q7IDIgICAgICAgIEFkZCBhIG5ldyBjb3cgd2l0aCBJRCAyXHJcbiAgICAgNyAgIHQgNCAgLSZndDsgWzUsMyw3XSAgICA9Jmd0OyA3ICAgICAgICBSZXZlcnQgdGltZSB0byBiZWZvcmUgcXVlcnkgNFxyXG4gICAgIDggICBhIDQgIC0mZ3Q7IFs1LDMsNyw0XSAgPSZndDsgNCAgICAgICAgQWRkIGEgbmV3IGNvdyB3aXRoIElEIDRcclxuICAgICA5ICAgcyAgICAtJmd0OyBbNSwzLDddICAgID0mZ3Q7IDcgICAgICAgIFNlbGwgcmVjZW50IGNvdyA0XHJcbiAgICAxMCAgIHQgNyAgLSZndDsgWzUsMl0gICAgICA9Jmd0OyAyICAgICAgICBSZXZlcnQgdGltZSB0byBiZWZvcmUgcXVlcnkgN1xyXG4gICAgMTEgICBzICAgIC0mZ3Q7IFs1XSAgICAgICAgPSZndDsgNSAgICAgICAgU2VsbCByZWNlbnQgY293IDJcclxuICAgIDEyICAgcyAgICAtJmd0OyBbXSAgICAgICAgID0mZ3Q7IC0xICAgICAgIFNlbGwgcmVjZW50IGNvdyA1PFwvcHJlPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBBIHNpbmdsZSBpbnRlZ2VyOiBOPFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLk4rMTogTGluZSBpKzE6IHF1ZXJ5IFFfaTxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lcyAxLi5OOiBMaW5lIGk6IFRoZSBJRCBvZiB0aGUgbW9zdCByZWNlbnRseSBwdXJjaGFzZWQgY293IGFmdGVyIHF1ZXJ5IGkgdGFrZXMgZWZmZWN0ICgtMSBpZiBubyBjb3dzIGFyZSBvd25lZCkuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Olympiad > USA Computing Olympiad > 2009-2010 Season > USACO US Open 2010 Contest > Silver 3번