Chapter 32 Final Test - Array Mastery (Bài kiểm tra cuối Ch32 - Array Mastery)

Source: Phước Hưng OJ

Version: Phuoc Hung OJ Extended

Problem

Maintain a fixed-capacity array of capacity $C$ with logical size $n$, so the active sequence is $a_0,\ldots,a_{n-1}$ and $0\le n\le C$.

Process $Q$ commands in order:

• 1 p: print $a_p$, with $0\le p<n$.
• 2 p x: assign $a_p\leftarrow x$.
• 3: reverse the logical sequence.
• 4 p x: insert $x$ before position $p$, with $0\le p\le n<C$.
• 5 p: delete position $p$, with $0\le p<n$.
• 6 x: print the smallest index containing $x$, or $-1$.
• 7: with $n>0$, print $S=\sum a_i$, $m=\min a_i$, and $M=\max a_i$.

All positions are 0-based. Updates affect all later commands.

Input

The first line contains $C,n,Q$. The second line contains the initial $n$ integers (empty if $n=0$). The next $Q$ lines contain commands.

Output

For every command of type 1, 6, or 7, print one result line.

Subtask

Subtask 1 (20 points): $1\le C\le10$, $1\le Q\le20$.

Subtask 2 (30 points): $1\le C\le100$, $1\le Q\le200$.

Subtask 3 (50 points): $1\le C\le2000$, $1\le Q\le5000$.

Example

Input

5 3 7
4 1 9
1 1
4 1 7
6 9
3
2 0 5
7
5 2

Output

1
3
17 1 7

Explanation

The sample follows the definitions and rules above.