Recently Segment Tree Test. After a long battle with his feelings, he realized he could no longer keep them bottled up.

revisited his long lost love,After many sleepless nights of browsing the internet, he finally came up with the problem. However, try as he might, the solution of the problem did not meet his standards, nor did they meet those of the other contestants.

Being extremely **persistent**, has decided to try once more in projecting his emotions onto his problems. Please free him from the burden of his emotions by answering the following queries:

`U pos val`

- Change the value from position`pos`

to value`val`

.`G x`

- Revert to revision`x`

.`P x y`

- Output the maximum prefix sum on the interval from`x`

to`y`

.`S x y`

- Output the maximum suffix sum on the interval from`x`

to`y`

.

At this point in time, `G`

and `U`

). The initial structure has the revision index .

#### Input Specification

On the first line of input you will find the integer , representing the size of the array.

On the second line of input you will find space-separated integers, representing the initial array. It is guaranteed that the total sum of the given numbers does not exceed .

On the third line of input, you will find the integer , representing the number of queries.

On the next lines of input, you will find queries formatted as specified above.

#### Output Specification

For each of the `P`

and `S`

queries, output its result on a single line by itself in order according to the input.

#### Sample Input

```
5
-1 -2 -3 -2 9
5
P 2 3
U 1 8
S 1 5
G 0
S 1 5
```

#### Sample Output

```
-2
10
9
```

## Comments

the array is indexed from 0 to N-1 or from 1 to N

The array is 1 indexed.