Little T has a very large bookshelf. The construction of this bookshelf is somewhat unique: the books are stacked in a single column from top to bottom. She has numbered each book with a positive integer from $1$ to $n$.

When Little T reads, she takes out a book, finishes reading it, puts it back on the bookshelf, and then takes out the next one. Because these books are so engaging, she often forgets exactly where a book was originally placed on the shelf after she finishes reading it. However, Little T has an excellent memory, so every time she puts a book back, she can at least place it near its original position. For example, if there were $X$ books above this book when she took it out, then when she puts it back, there will be either $X-1$, $X$, or $X+1$ books above it.

There are also special cases, such as when the phone rings or a friend visits while she is reading. In these cases, the careless Little T will simply place the book at the very top or the very bottom of the bookshelf before walking away.

Over time, the order of the books on Little T's shelf becomes increasingly chaotic, making it harder and harder to find a book with a specific ID. Therefore, she would like you to help her write a library management program to process her operations while reading and to answer two types of questions: (1) What is the position of the book with ID $X$ on the shelf? (2) What is the ID of the $i$-th book from the top?

Input

The first line contains two integers $n$ and $m$, representing the number of books and the number of commands, respectively. The second line contains $n$ positive integers, where the $i$-th number represents the ID of the book initially placed at the $i$-th position from the top. The following $m$ lines each contain a command. There are 5 types of commands:

1. Top S: Move the book with ID $S$ to the very top.
2. Bottom S: Move the book with ID $S$ to the very bottom.
3. Insert S T: $T \in \{-1, 0, 1\}$. If there are $X$ books above the book with ID $S$, this command means that after putting the book back, there are $X+T$ books above it.
4. Ask S: Query how many books are currently above the book with ID $S$.
5. Query S: Query the ID of the $S$-th book from the top.

Output

For every Ask or Query command, you should output one line containing a single integer representing the answer to the query.

Examples

Input 1

10 10 
1 3 2 7 5 8 10 4 9 6
Query 3 
Top 5 
Ask 6 
Bottom 3 
Ask 3 
Top 6 
Insert 4 -1 
Query 5 
Query 2 
Ask 2

Output 1

2
9
9
7
5
3

Constraints

• For 30% of the data, $n, m \le 10000$.
• For 100% of the data, $n, m \le 80000$.