At the Sushi Belt Lab, plates move on a circular belt. Each plate has an integer flavor value.

You need to process events on the current belt order.

• SHIFT k: rotate the belt by k positions to the right (if k is negative, rotate left).
• REVERSE: reverse the order of all sushi on the belt. After this operation, what was previously the right endpoint becomes the left endpoint, and what was previously the left endpoint becomes the right endpoint.
• SEASON d: add d to every plate's flavor value.
• TAKE c: remove one plate from an endpoint and print its current value.
  • c = L means the left endpoint.
  • c = R means the right endpoint.

It is guaranteed that every TAKE operation is valid.

Input

The first line contains two integers ~N~ and ~Q~, the initial number of plates and the number of operations.

The second line contains ~N~ integers ~v_1, v_2, \ldots, v_N~, the initial flavor values from left to right.

Each of the next ~Q~ lines is one operation in one of the following formats:

• SHIFT k
• REVERSE
• SEASON d
• TAKE c

Output

For each TAKE operation, print one line with the removed plate's current flavor value.

Constraints

• ~1 \le N \le 10^5~
• ~1 \le Q \le 4 \cdot 10^4~
• ~-10^{9} \le v_i \le 10^{9}~
• ~-10^{9} \le d \le 10^{9}~
• ~-10^{9} \le k \le 10^{9}~
• Throughout all operations, every plate value fits in signed 64-bit integer range.

Example 1

Input

5 8
3 1 4 1 5
TAKE L
SEASON 2
SHIFT 1
TAKE R
REVERSE
TAKE L
SHIFT -2
TAKE R

Output

3
3
6
7

Explanation

The belt evolves as:

• Start: [3, 1, 4, 1, 5]
• TAKE L: print 3, belt [1, 4, 1, 5]
• SEASON 2: [3, 6, 3, 7]
• SHIFT 1: [7, 3, 6, 3]
• TAKE R: print 3, belt [7, 3, 6]
• REVERSE: [6, 3, 7]
• TAKE L: print 6, belt [3, 7]
• SHIFT -2: unchanged (size 2)
• TAKE R: print 7