Problem Description

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

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

Operation 2: Given $l,r$, simultaneously modify $a_l,\dots,a_r$ to the value obtained by dividing by $2$ and taking the floor.

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

Input Format

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 one operation:

1 l r x means Operation 1.

2 l r means Operation 2.

3 l r means Operation 3.

Output Format

For each Operation 3, output one line containing one integer, which is the answer.

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

174
66
83
354
363
121
440

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

104
30
108
48
84
5

Hint

Warning: Misusing this problem will result in your account being banned.

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.

Translated by ChatGPT 5