D. Джейми и список дел
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Почему мне надо делать так много домашних заданий???

У Джейми очень много дел в школе. Он начинает забывать, какие домашние задания ему надо сделать, поэтому он решил записывать их в список дел. Каждому заданию он присваивает некоторый приоритет так, что чем приоритет меньше, тем важнее задание. Таким образом он сможет решить, на какие задания тратить больше времени.

Через несколько дней Джейми обнаружил, что его список дел настолько большой, что он не может им пользоваться самостоятельно. Так как вы дружите с Джейми, помогите ему и напишите программу, которая выполняет следующий операции со списком дел:

  • set ai xi — Добавить задание ai в список дел, если оно ещё не в списке, и назначить ему приоритет равный xi. Если задание ai уже в списке дел, его приоритет станет равен xi.
  • remove ai — Удалить задание ai из списка дел, если оно в нём есть.
  • query ai — Выведите количество заданий, которые важнее (имеют меньший приоритет), чем задание ai, чтобы Джейми смог лучше распределить своё время. Выведите  - 1 если задания ai в списке дел нет.
  • undo di — Отменить все изменения, сделанные за последние di дней (не включая день текущей операции)

В день с номером 0 список дел пуст. В каждый из следующих q дней Джейми будет делать ровно одну операцию одного из четырёх типов. Если операция — это query, то необходимо вывести ответ на запрос до начала обработки запроса, соответствующего следующему дню, чтобы Джейми смог заранее спланировать свой день.

Входные данные

В первой строке содержится целое число q (1 ≤ q ≤ 105) — количество операций.

Следующие q строк содержат описания запросов. В строке с номером i содержится описание запроса, который надо обработать в день i. Запрос имеет следующий формат:

Первое слово в строке обозначает тип операции. Он может быть равен set, remove, query или undo.

  • Если запрос имеет тип set, то далее задана строка ai и целое число xi (1 ≤ xi ≤ 109). ai — это название задания, которому необходимо установить приоритет priority xi.
  • Если запрос имеет тип remove, то далее задана строка ai. ai — это название задания, которое надо удалить из списка.
  • Если запрос имеет тип query, то далее задана строка ai. ai — это название задания, для которого надо найти требуемую величину.
  • Если запрос имеет тип undo, то далее задано целое число di (0 ≤ di < i). Этот запрос обозначает, что надо отменить действия за последние di дней.

Названия всех заданий ai состоят из строчный букв английского алфавита и имеют длину 1 ≤ |ai| ≤ 15.

Гарантируется, что последний запрос имеет тип query.

Выходные данные

Для каждого запроса типа query, выведите одно целое число — количество заданий, которые имеют приоритет меньше, чем ai, или  - 1, если задания ai нет в списке дел.

Протокол взаимодействия

Если операцимя имеет тип query, вам необходимо вывести ответ на запрос и сбросить буфер вывода до начала обработки следующей операции. В противном случае Вы можете получить вердикт Idleness Limit Exceed.

Для того, чтобы узнать, как сбросить буфер вывода, обратитесь к документации по Вашему языку программирования. Ниже приведён код для некоторых популярных языков программирования:

  • C: fflush(stdout);
  • C++: cout « flush;
  • Java: System.out.flush();
Примеры
Входные данные
8
set chemlabreport 1
set physicsexercise 2
set chinesemockexam 3
query physicsexercise
query chinesemockexam
remove physicsexercise
query physicsexercise
query chinesemockexam
Выходные данные
1
2
-1
1
Входные данные
8
set physicsexercise 2
set chinesemockexam 3
set physicsexercise 1
query physicsexercise
query chinesemockexam
undo 4
query physicsexercise
query chinesemockexam
Выходные данные
0
1
0
-1
Входные данные
5
query economicsessay
remove economicsessay
query economicsessay
undo 2
query economicsessay
Выходные данные
-1
-1
-1
Входные данные
5
set economicsessay 1
remove economicsessay
undo 1
undo 1
query economicsessay
Выходные данные
-1