Fafa and Array

Description:

Input:

The first line contains one integer n (3 ≤ n ≤ 10⁵) — the length of the array.

The second line contains n positive integers a₁, a₂, ..., a_n (0 < a_i ≤ 10⁹) — the array elements.

The third line contains an integer q (1 ≤ q ≤ 10⁵) — the number of queries.

Then q lines follow, line i describes the i-th query and contains four integers t_i l_i r_i x_i .

It is guaranteed that at least one of the queries is of type 1.

Output:

For each query of type 1, print the answer to the query.

Sample Input:

5
1 1 1 1 1
5
1 2 4 1
2 2 3 1
2 4 4 2
2 3 4 1
1 3 3 2

Sample Output:

2
8

Sample Input:

5
1 2 3 4 5
4
1 2 4 2
2 2 4 1
2 3 4 1
1 2 4 2

Sample Output:

6
10