RANGESUM - Range Sum


You are initially given an array of N integers (1 ≤ N ≤ 105). Given this array, you have to perform 2 kinds of operations:

(i) Operation 1 : Op1(l, r)

You are given 2 integers l and r. (1 ≤ l ≤ r ≤ current size of the array). You need to return the sum of all the elements with indices between l and r (both inclusive). That is, if the elements currently in the array are a1, a2, a3.... an, you need to return the following sum : al + al+1 + al+2 ... + ar.

(ii) Operation 2 : Op2(x)

You are given a single integer x (|x| ≤ 109). Add this element to the beginning of the array. After this operation, x will now become a1, the old a1 will now become a2, and so on. The size of the array will increase by 1.

Input

The first line contains a single integer N (1 ≤ N ≤ 105), the number of elements initially in the array.

This is followed by a line containing N space separated integers, a1 a2 ... aN. (|ai| ≤ 109)

The next line contains a single integer Q, the number of operations you will be asked to perform. (1 ≤ Q ≤ 105)

Q lines of input follow. Each such line starts with either the number 1 or the number 2. This indicates the type of operation that you are required to perform. The format of these queries are as follows:

1 l r : Carry out operation 1 with arguments l and r. (1 ≤ l ≤ r ≤ current size of the array)
That is, return the sum of the following array elements : al + al+1 ... + ar

2 x : Carry out operation 2 with the argument x. (|x| ≤ 109)
That is, add the value x at the beginning of the array.

Output

For each query of type 1, output the return value on a new line. No output needs to be printed for queries of type 2.

Example

Input #1:
10
1 2 3 4 5 6 7 8 9 10
4
1 1 10
1 1 1
1 10 10
1 2 7 Output #1:
55
1
10
27
Input #2:
5
6 7 8 9 10
9
2 5
2 4
1 2 7
2 3
2 2
2 1
1 1 10
1 1 1
1 10 10 Output #2:
45
55
1
10

hide comments
Shaka Shadows: 2013-07-31 20:17:31

There is a more general version of this problem on SPOJ. See http://www.spoj.com/problems/GSS6.

Last edit: 2013-07-31 20:52:15
BLANKRK: 2013-07-09 08:09:16

AC..gud one... :D

shiv prasad chabarval: 2013-06-22 10:15:59

@Gowri Sundarami: please check my code and tell me where it fails id:9528540

napster: 2013-06-22 06:21:35

@Gowri Sundarami: don't know why i'm getting WA.......please help me.My submission id is 9478119

shiva_hellgeek: 2013-06-15 10:25:24

finally got this one, so many conditions...
:D

Aditya Bahuguna: 2013-06-13 21:15:58

@Muh. Aunorafiq...long long fits everything in :)

Muh. Aunorafiq Musa: 2013-06-09 19:49:24

is the return value of op1 possible to use unsigned long long in C ?
so many thanks if someone replay :)

Last edit: 2013-06-12 18:02:06
Dominik Kempa: 2013-05-18 18:50:30

Some testcases have Q > 10^5.

Mitch Schwartz: 2013-04-28 12:33:30

I think the test data was modified after my submission (I was the first solver), although I guess there's a small possibility it wasn't and my 0.01 was just really lucky with server instability -- submitting the same exact code over and over now hasn't gotten 0.01 again, the best was 0.02.

Might as well have an accurate rank table; @Gowri, if the test data was modified, please rejudge just my 0.01 submission (ID 9152798), being sure to check "Refresh cached info about test sequence" if test sequence also changed.

Last edit: 2013-04-28 13:09:03

Added by:Gowri Sundaram
Date:2013-04-11
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64