Log Analysis

Lisa is building a log-analysis tool for a distributed computer system. Unlike a single-node log, which is append-only, a distributed log is highly volatile: when a node comes online it may push a batch of events into the past of the log, and when a node goes offline some of its entries may disappear.

To keep the tool stable and responsive, Lisa must track how many distinct event types appear in a segment of the log. She handles the distributed side; your job is the local engine.

Your program starts from an empty log and must support three operations:

• insert index number type — insert number events, all of type type, immediately before the event currently at position index. Every event that was at position index or later moves number positions to the right and is renumbered.
• remove index number — delete number consecutive events starting at position index.
• query index1 index2 — report how many distinct event types occur among the events at positions index1 through index2, inclusive.

Events are numbered from $1$. Each event type is a single lowercase letter.

The first line contains a single integer $n$ — the number of operations ($1 \le n \le 30000$).

Each of the next $n$ lines describes one operation. The line begins with an operation symbol — + for insert, - for remove, or ? for query — followed by that operation's arguments:

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

All indices are valid: every referenced event exists, and a remove never runs past the end of the log. For insert and remove, number does not exceed $10000$. Event types are lowercase Latin letters.

For each query, print a single line containing one integer — the number of distinct event types among the events at positions index1 through index2, inclusive.