Bookcase Management

Little T has a huge bookshelf that is arranged in a single vertical column. The books in the shelf are numbered from \(1\) to \(n\) from top to bottom initially. Every time Little T reads a book, she takes it out of the shelf, reads it, and then puts it back. However, after reading the book, she might forget its original position and may reinsert it slightly differently.

If, when she takes the book out, there are \(x\) books above it, then when putting it back she will typically place the book so that it has either \(x-1\), \(x\), or \(x+1\) books above it. In special situations, such as when she gets a phone call or has a visitor, she might instead reinsert the book at the very top or the very bottom of the shelf.

Your task is to implement a program to manage the bookshelf. There are two kinds of queries that you need to answer:

• Given a book number \(x\), determine its current 1-indexed position in the shelf (from top to bottom).
• Given a 1-indexed position \(i\), determine the number on the book at that position.

The operations are given in sequence. Initially, the shelf is arranged in increasing order from top to bottom, i.e. \(1,2,...,n\).

Operation formats:

• 1 x mode: A reading event. Book number x is taken out. If mode is an integer among \(-1, 0, 1\), then if the book was originally at position \(p\) (1-indexed), it will be reinserted at position \(p+d\) (adjusted to the boundaries if necessary). If mode is T, the book is reinserted at the top of the shelf. If mode is B, the book is reinserted at the bottom.
• 2 x: Query the current position (1-indexed) of book number x.
• 3 i: Query the number on the book at the i-th position from the top.

Input format:

• The first line contains two integers \(n\) and \(m\): the number of books and the number of operations, respectively.
• The following \(m\) lines each contain an operation in one of the formats described above.

Output format:

• For each query (operation of type 2 or 3), output the answer on a separate line, in the order the queries appear in the input.

inputFormat

The first line contains two integers \(n\) and \(m\) where \(n\) is the number of books and \(m\) is the number of operations.

Each of the next \(m\) lines represents an operation, and can be one of the following formats:

• 1 x mode: Book \(x\) is taken out and then reinserted. The mode can be either an integer (-1, 0, or 1) which means insert at position \(p+d\) (if \(p\) was the original position, adjusting for boundaries), or it can be T (for top) or B (for bottom).
• 2 x: Query the current 1-indexed position of book number \(x\).
• 3 i: Query the book number at the i-th position from top.

Note: The initial arrangement of the shelf is \(1, 2, \ldots, n\) from top to bottom.

outputFormat

For each query operation (type 2 and type 3), output the answer on a separate line.

sample

5 5
2 3
3 3
1 3 1
2 3
3 4

3
3
4
3

</p>