RMQ with Shifts

Source: UVa

Version: Phuoc Hung OJ Extended

Problem Statement

Given a 1-indexed array $A$, process two operation types. query(L,R) asks for the minimum on $[L,R]$. shift(i_1,i_2,\ldots,i_k) with $i_1<i_2<\cdots<i_k$ left-cyclically shifts the values at those positions.

Input

• The first line contains $n$ and $q$.
• The second line contains $n$ positive integers, each at most $100000$.
• Each of the next $q$ lines is a valid query(...) or shift(...) string, contains no spaces, and has length at most $30$.

Output

For every query operation, print the minimum value in the requested range.

Subtasks

• Subtask 1 — 20%: $1 \le n,q \le 1000$.
• Subtask 2 — 30%: $1 \le n,q \le 50000$.
• Subtask 3 — 50%: $1 \le n \le 100000$, $1 \le q \le 250000$.

Examples

Input

7 5
6 2 4 8 5 1 4
query(3,7)
shift(2,4,5,7)
query(1,4)
shift(1,2)
query(2,2)

Output

1
4
6

Explanation

The first query examines $4,8,5,1,4$, so the answer is $1$. After shift(2,4,5,7), the array becomes $6,8,4,5,4,1,2$, hence query(1,4) returns $4$. After shift(1,2), the first two values become $8,6$, so query(2,2) returns $6$.