Given a sequence $a_1, \dots, a_n$ of length $n$, you need to perform $m$ operations of three types:

Operation 1: Given $l, r, x$, first create a new array $b$ such that $b_i = a_i$, then update $a_x, \dots, a_{x+r-l}$ to be equal to $b_l, \dots, b_r$ respectively.

Operation 2: Given $l, r$, update $a_l, \dots, a_r$ by replacing each element with its value divided by $2$ (rounded down).

Operation 3: Given $l, r$, calculate the sum of $a_l, \dots, a_r$.

Input

The first line contains an integer $n$.

The next line contains $n$ integers representing the sequence $a_1, \dots, a_n$.

The next line contains an integer $m$.

The next $m$ lines each describe an operation:

1 l r x represents operation 1;

2 l r represents operation 2;

3 l r represents operation 3.

Output

For each operation 3, output one line containing an integer representing the answer.

Examples

Input 1

10
1 81 93 81 16 97 63 26 66 13
10
1 1 5 3
3 5 6
3 9 9
3 1 3
3 1 7
2 1 3
3 3 9
1 5 6 6
3 1 4
3 3 9

Output 1

174
66
83
354
363
121
440

Input 2

10
61 53 17 97 81 17 1 91 38 93
10
2 3 6
2 1 8
3 1 5
3 1 1
3 1 7
3 3 5
3 1 4
2 2 10
2 1 5
3 5 5

Output 2

104
30
108
48
84
5

Subtasks

For $100\%$ of the data, $1 \le n \le 3 \cdot 10^6$ and $1 \le m \le 3 \cdot 10^6$.

The initial values of the sequence satisfy $1 \le a_i \le 10^9$.

For each operation, $1 \le l \le r \le n$.

For each operation 1, $1 \le x \le x+r-l+1 \le n$.

All values above are integers.