There is an array of n numbers, indexed 1, 2, \ldots, n. Your task is to implement a data structure which has the following operators:

1. Increase every number in the range [a,b] by x
2. Set every number in the range [a,b] to be x
3. Compute the sum of numbers in the range [a,b]

Input

The first line of the input has single integer n, the size of the array.

The next line has n integers v_1, v_2, \ldots, v_n, the original content of the array.

Next line has single integer q, the number of queries.

The rest q lines each describe one query:

If the query type is 1, the line is of form "1 a b x". This means that every number in the range [a,b] needs to be increased by x.

If the query type is 2, the line is of form "2 a b x". This means that every number in the range [a,b] needs to be set to x.

If the query type is 3, the line is of form "3 a b". This means that you have to count the sum of numbers in the range [a,b].

Output

For each query of type 3, output the sum, one per line.

Limits

• 1 \le n \le 10^5
• -10^6 \le v_i \le 10^6
• 1 \le q \le 10^5
• 1 \le a \le b \le n
• -10^6 \le x \le 10^6

Example

Input:

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

Output:

7
11
15