RMQ với phép dịch vòng (RMQ with Shifts)

Nguồn: UVa

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho mảng $A$ đánh số từ $1$. Có hai loại thao tác. query(L,R) yêu cầu giá trị nhỏ nhất trên đoạn $[L,R]$. shift(i_1,i_2,\ldots,i_k) với $i_1<i_2<\cdots<i_k$ thực hiện dịch vòng trái các giá trị tại những vị trí đã nêu: giá trị cũ ở $i_2$ chuyển đến $i_1$, ..., và giá trị cũ ở $i_1$ chuyển đến $i_k$.

Input

• Dòng đầu chứa $n$ và $q$.
• Dòng thứ hai chứa $n$ số nguyên dương không vượt quá $100000$.
• Mỗi trong $q$ dòng tiếp theo là một chuỗi thao tác query(...) hoặc shift(...), không chứa khoảng trắng và có độ dài không quá $30$ ký tự. Mọi thao tác đều hợp lệ.

Output

Với mỗi thao tác query, in giá trị nhỏ nhất trên đoạn được hỏi.

Subtask

• 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$.

Ví dụ

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

Giải thích

Truy vấn đầu tiên xét các giá trị $4,8,5,1,4$ nên kết quả là $1$. Sau shift(2,4,5,7), mảng thành $6,8,4,5,4,1,2$; vì vậy query(1,4) cho $4$. Sau shift(1,2), hai giá trị đầu đổi chỗ thành $8,6$, nên query(2,2) cho $6$.