410271: GYM103997 A SuperMemo

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

A. SuperMemotime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Your friend, Jackson is invited to a TV show called SuperMemo in which the participant is told to play a memorizing game. At first, the host tells the participant a sequence of numbers, $$$\{A_1, A_2, \ldots A_n\}$$$. Then the host performs a series of operations and queries on the sequence which consists:

  • $$$ADD\ x\ y\ D$$$: Add $$$D$$$ to each number in sub-sequence $$$\{A_x \ldots A_y\}$$$. For example, performing "$$$ADD\ 2\ 4\ 1$$$" on $$$\{1, 2, 3, 4, 5\}$$$ results in $$$\{1, 3, 4, 5, 5\}$$$
  • $$$REVERSE\ x\ y$$$: reverse the sub-sequence $$${A_x \ldots A_y}$$$. For example, performing "$$$REVERSE\ 2\ 4$$$" on $$$\{1, 2, 3, 4, 5\}$$$ results in $$$\{1, 4, 3, 2, 5\}$$$
  • $$$REVOLVE\ x\ y\ T$$$: rotate sub-sequence $$${A_x \ldots A_y}$$$ $$$T$$$ times. For example, performing "$$$REVOLVE\ 2\ 4\ 2$$$" on $$$\{1, 2, 3, 4, 5\}$$$ results in $$$\{1, 3, 4, 2, 5\}$$$
  • $$$INSERT\ x\ P$$$: insert $$$P$$$ after $$$A_x$$$. For example, performing "$$$INSERT\ 2\ 4$$$" on $$$\{1, 2, 3, 4, 5\}$$$ results in $$$\{1, 2, 4, 3, 4, 5\}$$$
  • $$$DELETE\ x$$$: delete $$$A_x$$$. For example, performing "$$$DELETE\ 2$$$" on $$$\{1, 2, 3, 4, 5\}$$$ results in $$$\{1, 3, 4, 5\}$$$
  • $$$MIN\ x\ y$$$: query the participant what is the minimum number in sub-sequence $$$\{A_x \ldots A_y\}$$$. For example, the correct answer to "$$$MIN\ 2\ 4$$$" on $$$\{1, 2, 3, 4, 5\}$$$ is $$$2$$$

To make the show more interesting, the participant is granted a chance to turn to someone else that means when Jackson feels difficult in answering a query he may call you for help. You task is to watch the TV show and write a program giving the correct answer to each query in order to assist Jackson whenever he calls.

Input

The first line contains $$$n$$$ ($$$n \leq 100000$$$).

The following $$$n$$$ lines describe the sequence.

Then follows $$$M$$$ ($$$M \leq 100000$$$), the numbers of operations and queries.

The following $$$M$$$ lines describe the operations and queries.

Output

For each "$$$MIN$$$" query, output the correct answer.

ExamplesInput
5
1
2
3
4
5
2
ADD 2 4 1
MIN 4 5
Output
5
Input
10
1 2 3 4 5 6 7 8 9 10
15
ADD 4 8 3
MIN 5 7
MIN 7 10
REVERSE 2 5
MIN 2 6
MIN 2 3
INSERT 3 4
MIN 3 4
MIN 5 10
DELETE 6
MIN 3 5
MIN 4 4
REVOLVE 3 6 7
MIN 5 8
MIN 7 10
Output
8
9
2
7
4
2
3
4
7
9
Note

All input fits in 32-bit integers. Every number in the sequence after every operation fits in a 32-bit integer.

Source/Category

加入题单

算法标签: