_Why I have to finish so many assignments???_
Jamie is getting very busy with his school life. He starts to forget the assignments that he has to do. He decided to write the things down on a to-do list. He assigns a value _priority_ for each of his assignment **(lower value means more important)** so he can decide which he needs to spend more time on.
After a few days, Jamie finds out the list is too large that he can't even manage the list by himself! As you are a good friend of Jamie, help him write a program to support the following operations on the to-do list:
* _set_ _a__i_ _x__i_ — Add assignment _a__i_ to the to-do list if it is not present, and set its _priority_ to _x__i_. If assignment _a__i_ is already in the to-do list, its _priority_ **is changed** to _x__i_.
* _remove_ _a__i_ — Remove assignment _a__i_ from the to-do list if it is present in it.
* _query_ _a__i_ — Output the number of assignments that are more important (have a **smaller** _priority_ value) than assignment _a__i_, so Jamie can decide a better schedule. Output - 1 if _a__i_ is not in the to-do list.
* _undo_ _d__i_ — Undo all changes that have been made in the previous _d__i_ days (not including the day of this operation)
At day 0, the to-do list is empty. In each of the following _q_ days, Jamie will do **exactly one** out of the four operations. If the operation is a _query_, you should **output the result of the query before proceeding to the next day**, or poor Jamie cannot make appropriate decisions.
## Input
The first line consists of a single integer _q_ (1 ≤ _q_ ≤ 105) — the number of operations.
The following _q_ lines consists of the description of the operations. The _i_\-th line consists of the operation that Jamie has done in the _i_\-th day. The query has the following format:
The first word in the line indicates the type of operation. It must be one of the following four: _set_, _remove_, _query_, _undo_.
* If it is a _set_ operation, a string _a__i_ and an integer _x__i_ follows (1 ≤ _x__i_ ≤ 109). _a__i_ is the assignment that need to be set to _priority_ _x__i_.
* If it is a _remove_ operation, a string _a__i_ follows. _a__i_ is the assignment that need to be removed.
* If it is a _query_ operation, a string _a__i_ follows. _a__i_ is the assignment that needs to be queried.
* If it is a _undo_ operation, an integer _d__i_ follows (0 ≤ _d__i_ < _i_). _d__i_ is the number of days that changes needed to be undone.
All assignment names _a__i_ only consists of lowercase English letters and have a length 1 ≤ |_a__i_| ≤ 15.
It is guaranteed that the last operation is a _query_ operation.
## Output
For each _query_ operation, output a single integer — the number of assignments that have a priority lower than assignment _a__i_, or - 1 if _a__i_ is not in the to-do list.
[samples]
## Interaction
If the operation is a _query_, you **should** output the result of the query and flush the output stream before proceeding to the next operation. Otherwise, you may get the verdict _Idleness Limit Exceed_.
For flushing the output stream, please refer to the documentation of your chosen programming language. The flush functions of some common programming languages are listed below:
* C: _fflush(stdout);_
* C++: _cout « flush;_
* Java: _System.out.flush();_
_为什么我得完成这么多作业啊？_
Jamie 的学校生活变得非常忙碌。他开始忘记自己需要完成的作业。于是他决定把事情写在待办清单上，并为每项作业分配一个 _优先级_ 值（值越小表示越重要），以便决定哪些作业需要花更多时间。
几天后，Jamie 发现清单太长了，以至于他自己都难以管理！作为 Jamie 的好朋友，请你帮他写一个程序，支持对待办清单进行以下操作：
在第 #cf_span[0] 天，待办清单为空。在接下来的 #cf_span[q] 天中，Jamie 每天恰好执行以下四种操作之一。如果操作是 #cf_span[query]，你必须在进入下一天之前 *输出该查询的结果*，否则可怜的 Jamie 将无法做出合适的决策。
第一行包含一个整数 #cf_span[q] #cf_span[(1 ≤ q ≤ 105)] —— 操作的数量。
接下来的 #cf_span[q] 行描述了这些操作。第 #cf_span[i] 行描述了 Jamie 在第 #cf_span[i] 天执行的操作。查询操作的格式如下：
每行的第一个单词表示操作类型，必须是以下四种之一：_set_、_remove_、_query_、_undo_。
所有作业名称 #cf_span[ai] 仅由小写英文字母组成，长度满足 #cf_span[1 ≤ |ai| ≤ 15]。
保证最后一个操作是 _query_ 操作。
对于每个 _query_ 操作，输出一个整数 —— 优先级低于作业 #cf_span[ai] 的作业数量，如果 #cf_span[ai] 不在待办清单中，则输出 #cf_span[ - 1]。
如果操作是 #cf_span[query]，你 *必须* 输出查询结果并刷新输出流，然后再进行下一个操作。否则，你可能会得到 _Idleness Limit Exceed_ 的评测结果。
关于刷新输出流，请参考你所选编程语言的文档。以下是一些常见编程语言的刷新函数：
## Input
第一行包含一个整数 #cf_span[q] #cf_span[(1 ≤ q ≤ 105)] —— 操作的数量。接下来的 #cf_span[q] 行描述了这些操作。第 #cf_span[i] 行描述了 Jamie 在第 #cf_span[i] 天执行的操作。操作格式如下：
每行的第一个单词表示操作类型，必须是以下四种之一：_set_、_remove_、_query_、_undo_。
如果是 _set_ 操作，后面跟一个字符串 #cf_span[ai] 和一个整数 #cf_span[xi] #cf_span[(1 ≤ xi ≤ 109)]，表示将作业 #cf_span[ai] 的优先级设置为 #cf_span[xi]。
如果是 _remove_ 操作，后面跟一个字符串 #cf_span[ai]，表示移除作业 #cf_span[ai]。
如果是 _query_ 操作，后面跟一个字符串 #cf_span[ai]，表示查询作业 #cf_span[ai]。
如果是 _undo_ 操作，后面跟一个整数 #cf_span[di] #cf_span[(0 ≤ di < i)]，表示需要撤销过去 #cf_span[di] 天内的所有变更。
所有作业名称 #cf_span[ai] 仅由小写英文字母组成，长度满足 #cf_span[1 ≤ |ai| ≤ 15]。
保证最后一个操作是 _query_ 操作。
## Output
对于每个 _query_ 操作，输出一个整数 —— 优先级低于作业 #cf_span[ai] 的作业数量，如果 #cf_span[ai] 不在待办清单中，则输出 #cf_span[ - 1]。
[samples]
## Interaction
如果操作是 #cf_span[query]，你 *必须* 输出查询结果并刷新输出流，然后再进行下一个操作。否则，你可能会得到 _Idleness Limit Exceed_ 的评测结果。
关于刷新输出流，请参考你所选编程语言的文档。以下是一些常见编程语言的刷新函数：
C: _fflush(stdout);_
C++: _cout << flush;_
Java: _System.out.flush();_
**Definitions:**
- Let $ L $ be a dynamic multiset of assignments, where each assignment is a tuple $ (a_i, p_i) $, with $ a_i \in \Sigma^{1..15} $ (assignment name, lowercase English letters) and $ p_i \in \mathbb{Z}^+ $ (priority, lower value = more important).
- Let $ Q $ be a sequence of $ q $ operations ($ 1 \leq q \leq 10^5 $).
**Operations:**
1. **set $ a_i $ $ p_i $:**
Insert or update assignment $ a_i $ with priority $ p_i $:
$ L \leftarrow L \cup \{(a_i, p_i)\} $ (if $ a_i $ exists, update its priority to $ p_i $).
2. **remove $ a_i $:**
Remove assignment $ a_i $ from $ L $, if present:
$ L \leftarrow L \setminus \{(a_i, p) \mid p \in \mathbb{Z}^+\} $.
3. **query $ a_i $:**
If $ a_i \notin \text{dom}(L) $, output $ -1 $.
Otherwise, output:
$$
\left| \left\{ (a_j, p_j) \in L \mid p_j < p_i \right\} \right|
$$
where $ p_i $ is the priority of $ a_i $ in $ L $.
4. **undo:**
Revert the state of $ L $ to the state it had immediately before the most recent operation (i.e., maintain a versioned history of $ L $; undo the last non-undo operation).
**Initial State:**
$ L_0 = \emptyset $
**Constraints:**
- The last operation is guaranteed to be a `query`.
- All operations are performed sequentially; `undo` affects the state of $ L $, not the history of operations.
- For each `query`, output the result immediately and flush the output stream.
**Objective:**
Process each operation in sequence, maintaining the state of $ L $ and correctly answering each `query` as defined.