Order statistic set

Source: SPOJ

Version: Phuoc Hung OJ Extended

Problem Statement

Maintain a dynamic set $S$ of integers, initially empty. There are $Q$ operations:

• I x: insert $x$ if $x\notin S$.
• D x: delete $x$ if $x\in S$.
• K k: print the $k$-th smallest element of $S$.
• C x: print the number of elements of $S$ smaller than $x$.

If K k has $k>|S|$, print invalid.

Input

The first line contains $Q$.

Each of the next $Q$ lines contains one operation. For a value parameter $x$, $|x|\le10^9$. For a rank parameter $k$, $1\le k\le10^9$.

Output

Print the answer to every K or C query on its own line.

Subtasks

• Subtask 1 — 20%: $1\le Q\le50$.
• Subtask 2 — 30%: $1\le Q\le5000$.
• Subtask 3 — 50%: $1\le Q\le2\cdot10^5$.

Examples

Input

8
I -1
I -1
I 2
C 0
K 2
D -1
K 1
K 2

Output

1
2
2
invalid

Explanation

The sample is processed in order; every printed item/line corresponds to an operation that requires output.