연산

값이 0으로 초기화되어 있고 인덱스가 0부터 시작하는 정수 배열 $A$에 대해 다음 세 함수가 주어진다.

• 더하기 (key, value): $A[key]$의 값을 value만큼 더한다. 리턴하는 값은 $A[key]$가 아니라, 배열 $A$ 값 전체의 합이다.
• 구간합 (key1, key2): $key1 \le i \le key2$인 모든 $i$에 대한 $A[i]$의 구간합을 리턴한다. ($key1 \le key2$)
• 삭제 (key): $A[key]$의 값을 0으로 만든다. 리턴하는 값은 역시 해당 연산 이후 배열 $A$ 값 전체의 합이다.

연산을 수행할 때마다 리턴값을 출력하는 프로그램을 작성하시오.

예를 들어 아래와 같은 12개의 연산을 순서대로 적용한다고 해보자. 화살표 이후에 나타나는 값이 바로 당신의 프로그램이 출력해야 하는 값이다.

• 더하기 (key=27, value=30) → 30
• 더하기 (key=25, value=40) → 70
• 삭제 (key=17) → 70
• 더하기 (key=17, value=20) → 90
• 더하기 (key=5, value=50) → 140
• 구간합 (key1=10, key2=20) → 20
• 구간합 (key1=25, key2=30) → 70
• 삭제 (key=25) → 100
• 삭제 (key=17) → 80
• 더하기 (key=27, value=20) → 100
• 구간합 (key1=10, key2=20) → 0
• 구간합 (key1=25, key2=30) → 50

총 $n$개의 연산이 주어졌을 때, 각 연산을 적용한 이후 올바른 값을 출력하는 프로그램을 작성하시오.

첫 줄에 연산의 수 $n$이 주어진다.

각 연산은 종류에 따라 아래와 같은 형태로 한 줄에 하나씩 주어진다.

• 더하기: 줄의 첫 입력으로 1이 주어지고, 이후에 key와 value가 공백으로 구분되어 주어진다.
• 구간합: 줄의 첫 입력으로 2가 주어지고, 이후에 두 개의 key가 공백으로 구분되어 주어진다.
• 삭제: 줄의 첫 입력으로 3이 주어지고, 이후에 key가 주어진다.

한 줄에 각 함수의 리턴값을 공백으로 구분해서 출력해야 한다.

입출력 방식이 느리면 여러 줄을 입력받거나 출력할 때 시간초과가 날 수 있다.

C++을 사용하고 있고 cin/cout을 사용하고자 한다면, cin.tie(NULL)과 sync_with_stdio(false)를 둘 다 적용해 주고, endl 대신 개행문자(\n)를 쓰자. 단, 이렇게 하면 더 이상 scanf/printf/puts/getchar/putchar 등 C의 입출력 방식을 사용하면 안 된다.

Java를 사용하고 있다면, Scanner와 System.out.println 대신 BufferedReader와 BufferedWriter를 사용할 수 있다. BufferedWriter.flush는 맨 마지막에 한 번만 하면 된다.

Python을 사용하고 있다면, input 대신 sys.stdin.readline을 사용할 수 있다. 단, 이때는 맨 끝의 개행문자까지 같이 입력받기 때문에 문자열을 저장하고 싶을 경우 .rstrip()을 추가로 해 주는 것이 좋다.