给定一个长度 $n$ 的序列 $a_1,\dots,a_n$，需要进行 $m$ 次操作，操作共有三种类型：

操作 1：给定 $l,r,x$，先新建一个数组 $b$ 满足 $b_i=a_i$，之后将 $a_x,\dots,a_{x+r-l}$ 同时修改为 $b_l,\dots,b_r$；

操作 2：给定 $l,r$，将 $a_l,\dots,a_r$ 同时修改为除以 $2$ 下取整后的值；

操作 3：给定 $l,r$，求 $a_l,\dots,a_r$ 的和。

输入格式

第一行一个整数 $n$。

接下来一行 $n$ 个整数表示序列 $a_1,\dots,a_n$。

接下来一行一个整数 $m$。

接下来 $m$ 行，每行表示一个操作：

1 l r x 表示操作 1；

2 l r 表示操作 2；

3 l r 表示操作 3。

输出格式

对每个操作 3，输出一行，包含一个整数，表示答案。

样例数据

样例 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

样例 1 输出

174
66
83
354
363
121
440

样例 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

样例 2 输出

104
30
108
48
84
5

子任务

对于 $100\%$ 的数据，满足 $1\le n\le 3\cdot 10^6$，$1\le m\le 3\cdot 10^6$。

序列的初值满足 $1\le a_i\le 10^9。$

对每个操作满足 $1\le l\le r\le n$。

对每个操作 1 满足 $1\le x\le x+r-l+1\le n$。

以上所有数值为整数。