7781번 - Log Analysis 다국어

문제

Lisa writes a log analysis application for a distributed computer system. Unlike single-node logs, that are append-only the distributed log is highly volatile. When a node becomes online, it may push a batch of events in the past of the log. Conversely, when it goes offline some log entries may disappear.

To ensure the stability and availability of the application Lisa need to monitor the number of distinct events in the log segments. She is going to handle distributed part, while you have to implement a local one.

Your program is started from the empty log and must support the following operations:

• insert ⟨index⟩ ⟨number⟩ ⟨type⟩ — inserts ⟨number⟩ of events of type ⟨type⟩ before event with index ⟨index⟩. Events with indices larger or equal to ⟨index⟩ are renumbered.
• remove ⟨index⟩ ⟨number⟩ — removes ⟨number⟩ of events starting from event with index ⟨index⟩.
• query ⟨index₁⟩ ⟨index₂⟩ — counts the number of distinct event types for events with indices from ⟨index₁⟩ to ⟨index₂⟩ inclusive.

The events are indexed starting from 1. The event types are represented by single-letter codes.

입력

The first line of the input file contains single integer number n — the number of operations (1 ≤ n ≤ 30 000). The following n lines contain one operation description each.

Operation description starts with operation type: ‘+’ for insert, ‘-’ for remove and ‘?’ for query. Operation type is followed by operation arguments.

All indices are valid, i. e. events with specified indices exist, and you never have to remove events past the end of the log.

The ⟨number⟩ for the insert and remove operations does not exceed 10 000.

Event types are represented by lowercase Latin letter.

출력

For each query operation output a single number — the number of distinct event types between ⟨index₁⟩ and ⟨index₂⟩ inclusive.

제한

힌트