### Problem Statement You are initially given an array of N integers ( 1<=N<=10 $ ^{5} $ ). 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 a $ _{1} $ , a $ _{2} $ , a $ _{3} $ .... a $ _{n} $ , you need to return the following sum : a $ _{l} $ + a $ _{l+1} $ + a $ _{l+2} $ ... + a $ _{r} $ . (ii) Operation 2 : Op2( x ) You are given a single integer x ( |x| <= 10 $ ^{9} $ ). Add this element to the beginning of the array. After this operation, x will now become a $ _{1} $ , the old a $ _{1} $ will now become a $ _{2} $ , and so on. The size of the array will increase by 1. ### Input The first line contains a single integer N ( 1 <= N <= 10 $ ^{5} $ ), the number of elements initially in the array. This is followed by a line containing N space separated integers, a $ _{1} $ a $ _{2} $ .... a $ _{N} $ . ( |a $ _{i} $ | <= 10 $ ^{9} $ ) The next line contains a single integer Q, the number of operations you will be asked to perform. ( 1 <= Q <= 10 $ ^{5} $ ) 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 : a $ _{l} $ + a $ _{l+1} $ ... + a $ _{r} $ 2 x : Carry out operation 2 with the argument x. ( |x| <= 10 $ ^{9} $ ) 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.

SP14543 RANGESUM - Range Sum

Description

Input Format

Output Format