O. Логирование

Список событий изначально пуст. Каждое событие имеет тип — строчную латинскую букву. Обрабатывайте операции:

• + i k c — вставить $k$ событий типа $c$ так, чтобы первое из них оказалось на позиции $i$;
• - i k — удалить $k$ событий, начиная с позиции $i$;
• ? i j — вывести количество различных типов на позициях от $i$ до $j$.

События нумеруются с единицы; все операции корректны.

В первой строке — число операций $n$ ($1 \le n \le 3 \cdot 10^4$). Далее $n$ операций. Количество вставляемых или удаляемых за одну операцию событий $k$ не превосходит $1000$, а суммарное количество вставленных событий за всё время не превосходит $2 \cdot 10^5$.

На каждый запрос ? выведите количество различных типов на отрезке.