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