题目内容

给出一个长度为$n$的整数数组$a$，下标从$1$开始。

$q$次询问，每次询问给出两个区间 $[l_1,r_1],[l_2,r_2]$，先让下标在$[l_1,r_1]$里的元素乘以$2$，再让下标在$[l_2,r_2]$里的元素乘以 $2$，输出每次询问操作后数组总和是多少?

询问是相互独立的，每次询问后都把数组还原为初始状态。

输入描述

第一行包含两个整数$n$ $q(1≤n,q≤2×10^5)$，表示数组大小和询问个数。

第二行包含 $n$ 个整数 $a_i(-10^5 ≤ a_i≤ 10^5)$，表示数组 $a$。

接下来$q$行，每行四个整数$l_1$ $r_1$ $l_2$ $r_2$ $(1 ≤ l_1 ≤ r_1 ≤ n , 1 ≤ l_2 ≤ r_2 ≤ n)$，表示操作区间。

输出描述

输出包含$q$行，每行一个整数，表示每次询问操作后的数组总和。

样例1

输入

3 2
1 2 1
1 2 2 3
1 1 2 2

输出

12
7

说明

第一次询问:$[1,2]$ 内元素乘 $2$，$a=[2,4,1]$，$[2,3]$ 内元素乘 $2$，$a=「2,8,2]$，数组总和是 $12$。

第二次询问:$[1,1]$内元素乘 $2$，$a=[2,2,1]$，$[2,2]$内元素乘 $2$，$a=[2,4,1]$，数组总和是 $7$。