Goku is in a fight with Kid Buu. He is the toughest of all the opponents that Goku has faced all his life.

In between all his attacks at Goku, whenever Kid Buu feels tired and needs to take rest, he throws an array and some queries at Goku, who needs to solve the queries as quickly as possible. Since the queries thrown by Kid Buu are hard for Goku to solve, he is taking a lot of time to solve them, enabling Buu to rest more and attack Goku with even more force after he has answered all the queries. Goku is struggling to keep up the fight now. He needs your help.



Can you help him in solving the queries as fast as possible, so that Goku also gets some rest and is able to defeat his enemy?

You receive an array from Kid Buu, and the type of queries are as follows :

Type 1 : In query type 1, you get two integers, i and x. You need to add x to a_i.
Type 2 : In query type 2, you get two integers, l and r. You need to find and print the sum of all the elements a_i, where,
l ≤ i < r.
Type 3 : In query type 3, you have to reverse the current array.
Type 4 : In query type 4, you get an integer v. You need to replace the array with the array which you got after processing query number v.

You have to solve the queries and print the answer for every query of type 2 in a separate line.

Input :

First line contains an integer n, the size of the array.
Second line contains n space separated integers, the array.
Third line contains an integer, q, denoting the number of queries.
Each of the following q lines specify the query:
Each query has an integer at the beginning, specifying the type of the query, followed by 0, 1 or 2 more integers depending upon the type of the query as defined above.

Output :

For each query of type 2, output the result in a separate line.

Constraints :

1 ≤ n ≤ 10⁵
1 ≤ q ≤ 10⁵
|a_i|,|x| ≤ 10⁹
type is one of {1,2,3,4}
i, l, r and v will have appropriate values.