덱 조작과 쿼리

면접 대비

시간 제한2초메모리 제한1024 MB

요약

카드 덱에 push, pop, 이전 행동 시점의 상태로 되돌리는 restore, 합을 출력하는 print를 N개 처리하고 각 print마다 현재 덱의 합을 출력합니다.

난이도: 보통10점 중 5점
유형: 트리, 스택, 구현
정답자: 아직 제출이 없습니다

문제

하넬은 카드게임의 덱(deck)을 조작하는 방법을 연구하고 있다. 덱은 위와 아래가 있는 카드의 리스트이고, 각 카드에는 $0$ 이상 $10^9$ 이하의 정수가 하나씩 적혀 있다. 덱은 처음에 카드가 없는 빈 상태이다. 하넬은 현재 덱에 다음 네 가지 중 하나의 행동을 적용해 덱의 상태를 바꾸고자 한다.

push $x$ : $x$ 가 적힌 카드를 덱의 가장 위에 둔다. $(0 \le x \le 10^9)$
pop: 덱의 가장 위에서 카드를 제거한다. 덱에 카드가 없을 때는 pop이 주어지지 않는다.
restore $i$ : 현재 덱의 상태를 $i$ 번째 행동 이후의 덱 상태와 같게 만든다. $i$ 가 $0$ 이면 덱을 카드가 없는 초기 상태로 되돌린다. $i$ 번째 행동이 아직 이루어지지 않았을 때는 주어지지 않는다.
print: 현재 덱에 있는 모든 카드에 적힌 수의 합을 출력한다. 덱에 카드가 하나도 없으면 $0$ 을 출력한다.

입력

첫 번째 줄에 행동의 수 $N$ 이 주어진다. $(1 \le N \le 500\,000)$

두 번째 줄부터 $N$ 개의 줄에 걸쳐 행동이 위에 적힌 형식대로 한 줄에 하나씩 주어진다. push와 $x$ 사이, restore와 $i$ 사이에는 공백이 하나씩 들어간다. print 행동은 반드시 하나 이상 주어진다.

출력

print 행동이 주어질 때마다 덱에 있는 카드에 적힌 수의 합을 한 줄에 하나씩 출력한다.

예제2

예제 1
입력
```
5
print
push 10
push 20
pop
print
```
예상 출력
```
0
10
```

예제 2

입력

11
push 10
push 20
push 30
print
pop
pop
print
restore 3
pop
push 40
print

예상 출력

60
10
70