给定一个长度 $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$。
以上所有数值为整数。