Informatica Online Judge

  순천의 왕, 세빈 [2405 / 0965]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 5   Total Tried : 3


The Champion of this Problem (C++) : gs17018 - ms / 1825byte
My Best Submission (C++) : N/A

[35th 고동현]
Writer ID : [gs17003]

Background

대표적인 인싸 세빈이는 순천에서는 왕으로 군림한다.

그가 순천에 발을 딛는 순간 셀 수 없이 많은 여자들이 그를 보기 위해 줄을 선다. 시간이 갈수록 더 많은 여자들이 줄을 서자 세빈이는 골치가 아파졌다.

그래서 그는 "예약제"를 도입했다. 예약제에 따라 앞으로 모든 여자들은 세빈이를 만나기 전에 예약을 해야만 하게 되었다. 여자들은 다음과 같이 예약을 할 수 있다.

"t부터 d동안 세빈이를 만날 것이다."->"+ t d" 그리고 모든 여자들은 세빈이와 독대하는 것을 원하기 때문에 앞의 여자와의 만남이 모두 끝난 이후에 그를 만날 수 있다.

이때 여자들은 시점 t에 세빈이를 방문하게 되며 모두 다른 시간에 그를 찾아온다.

또한 그들은 인내심도 굉장히 좋기 때문에 앞의 여자와의 만남이 모두 끝나기만을 기다린 후 d동안 세빈이와 만난다.

하지만 그들은 굉장히 변덕스러워서 만남을 언제든 취소할 수 있다. 따라서 세빈이와의 만남을 주관하는 예약센터의 직원 민제는 그들을 상대하느라 머리가 매우 아프다.

그런데, 어느 날 세빈이의 베프 동현이가 순천에 내려왔다. 그 역시 예외 없이 예약을 해야 했다. 따라서 그는 민제를 찾아갔지만 민제는 여자들을 상대하기도 벅차다.

만약 동현이가 다른 여자들과 동시에 방문했다면 동현이는 여자를 먼저 만나게 해준다. 이때 여러분이 동현이가 세빈이를 만나려면 얼마나 기다려야 하는지 알려주자.

Input

첫째줄에 쿼리 개수 q가 주어진다. (1<=q<=300,000)

두 번째 줄부터 q+1 번째 줄까지 쿼리가 주어진다. 쿼리는 다음과 같이 3개의 종류로 구성된다.

"+ t d" (1<=t,d<=1,000,000) : 새로운 여자가 t에 방문할 것이고 d동안 만날 것이라고 예약했다.

"- i" (1<=i<=q) : 여자가 세빈이와의 만남을 취소했다. (i번째 쿼리의 여성이 만남을 취소한다.)

"? t" (1<=t<=1,000,000) 동현이가 민제에게 얼마나 기다려야 하냐고 물어봤다.

Output

"? t" 쿼리가 주어질 때마다 동현이가 세빈이를 만나기 위해 기다려야 하는 시간을 출력하라.

IO Example

Input
19
? 3
+ 2 2
? 3
? 4
+ 5 2
? 5
? 6
+ 1 2
? 2
? 3
? 4
? 5
? 6
? 7
? 9
- 8
? 2
? 3
? 6

Output
0
1
0
2
1
3
2
1
2
1
0
0
2
1
1

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]