로그 분석

Lisa는 분산 컴퓨터 시스템을 위한 로그 분석 도구를 만들고 있다. 단일 노드의 로그는 뒤에만 덧붙는(append-only) 반면, 분산 로그는 매우 변덕스럽다. 어떤 노드가 온라인이 되면 로그의 과거 위치에 이벤트 묶음을 밀어 넣을 수 있고, 반대로 노드가 오프라인이 되면 일부 로그 항목이 사라질 수 있다.

도구를 안정적이고 빠르게 유지하기 위해, Lisa는 로그의 특정 구간에 나타나는 서로 다른 이벤트 종류의 개수를 추적해야 한다. 분산 처리는 Lisa가 맡고, 여러분은 로컬 엔진을 구현하면 된다.

프로그램은 빈 로그에서 시작하며, 다음 세 가지 연산을 지원해야 한다.

• 삽입(insert) index number type — 현재 index 위치에 있는 이벤트 바로 앞에 종류가 type인 이벤트를 number개 삽입한다. index 이상의 위치에 있던 모든 이벤트는 오른쪽으로 number칸 밀려 다시 번호가 매겨진다.
• 삭제(remove) index number — index 위치부터 연속한 이벤트 number개를 지운다.
• 질의(query) index1 index2 — index1부터 index2까지(양 끝 포함) 위치에 있는 이벤트들 중 서로 다른 종류가 몇 가지인지 센다.

이벤트의 위치 번호는 $1$부터 시작한다. 각 이벤트 종류는 하나의 소문자 알파벳으로 표현된다.

첫 줄에는 연산의 개수 $n$이 주어진다 ($1 \le n \le 30000$).

이어지는 $n$개의 줄에는 각각 하나의 연산이 주어진다. 각 줄은 연산 기호로 시작하며 — 삽입은 +, 삭제는 -, 질의는 ? — 그 뒤에 해당 연산의 인자가 온다.

• + index number type
• - index number
• ? index1 index2

모든 인덱스는 유효하다. 즉 연산이 가리키는 이벤트는 항상 존재하며, 삭제 연산이 로그의 끝을 넘어가는 일은 없다. 삽입과 삭제 연산의 number는 $10000$을 넘지 않는다. 이벤트 종류는 소문자 알파벳이다.

각 질의마다 한 줄에 정수 하나를 출력한다 — index1부터 index2까지(양 끝 포함)에 있는 서로 다른 이벤트 종류의 개수.