Range Update and Range Sum Queries using Fenwick Tree

You are given an array of n integers and are required to process a series of queries on this array. There are two types of queries:

• Range Update: Given indices l and r and an integer x, add x to each element from index l to r (inclusive).
• Range Sum Query: Given indices l and r, output the sum of all elements from l to r.

To efficiently handle these operations, you should implement a Fenwick Tree (Binary Indexed Tree) with two trees. The core update operation uses the formula $$index = index + (index \& - index)$$ to navigate through the tree. Solve all queries and output the result for each range sum query in the order they are received.

inputFormat

The input consists of multiple lines:

1. The first line contains a single integer n, the number of elements in the array.
2. The second line contains n space-separated integers representing the initial array.
3. The third line contains a single integer q, the number of queries.
4. Each of the following q lines represents a query in one of the following two formats:
   • If the query is of type 1 (range update): 1 l r x, meaning add x to each element in the range [l, r].
   • If the query is of type 2 (range sum query): 2 l r, meaning output the sum of the elements in the range [l, r].

outputFormat

For every query of type 2, output the sum of the specified range on a new line.

## sample

5
2 1 5 3 4
1
2 1 3

8

</p>