## RANGESUM - Range Sum

### Problem Statement

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:
101 2 3 4 5 6 7 8 9 1041 1 101 1 11 10 101 2 7Output #1:5511027Input #2:56 7 8 9 1092 52 41 2 72 32 22 11 1 101 1 11 10 10Output #2:4555110``` naruto09: 2016-03-28 05:27:15 awesome problem..learned something new..;) Divyaanand Sinha: 2016-01-07 13:46:18 Is the array sorted? baranowski: 2016-01-06 13:33:28 This is driving me crazy... Nice O(n+q) solution in C++, and I'm getting TLE around test case #5. hodobox: 2015-12-03 20:49:39 Nice problem :) can be done with O(1) for both querries, and then you can just take the reversed array from input and process it all as type 2 querry :P dwij28: 2015-08-29 16:40:21 O(1) for all queries. AC. A few months back I would have never solved this question. Time helps us evolve and get better .. :) Last edit: 2016-10-07 09:30:22 kumar saurav sinha: 2015-06-24 16:54:52 AC in first attempt :D........ good question though....... Abhilash: 2015-06-23 12:49:34 easy pingal tirkey: 2015-05-23 18:33:22 Be careful I assumed numbers in array to be positive which caused me 6 WA! But enjoyed solving it :) Last edit: 2015-05-23 18:42:52 :.Mohib.:: 2014-12-25 20:46:34 AC in first attempt.... :) saanc: 2014-11-04 05:25:57 some test files have q>100000.Problem setter should not do this