给出$n$个数，现对这$n$个数进行$m$次操作，每次操作为将[$x_1,y_1$]区间所有数加上$z$或者减少$z$。

最后询问区间[$x_2,y_2$]的和。

输入

第一行输入$n,m$。$n \leq 100000,m \leq100000$

接下来一行为$n$个数。

接下来$m$行，每行四个数$t,x_1,y_1,z$

• $t=1$表示区间[$x,y$]所有数增加$z$
• $t=2$表示区间[$x,y$]所有数减少$z$。
• $z$为$int$范围内的数

最后一行，两个数$x_2,y_2$，询问区间[$x_2,y_2$]的和。

输出

输出询问结果。

样例

样例输入1

5 3
1 2 3 4 5
1 2 3 4
2 1 1 5
1 4 5 2
1 3

样例输出1

9