题目描述

Ant-land 最开始只有 1 座城镇。之后每当某座蚂蚁城镇过于拥挤时，就会有一部分居民搬出，建立一座新城镇。每建立新城镇时，都会立即建好 M 个蚁丘，编号为 1..M。

如果新城镇由旧城镇 P 分裂而来，那么新城镇初始时第 t 个蚁丘的容量与 P 城镇中第 t 个蚁丘相同。但在建城的同时，蚂蚁首领会下令：把编号在某个区间 [L,R] 内的所有蚁丘容量同时增加 V。

建好后，又会选出一个“高档社区”，它由某个区间 [i,j] 内的蚁丘组成。我们记这个新区间内所有蚁丘容量之和为 S。这个 S 会影响下一座新城的参数生成。

你的任务是：对每次新建城镇，输出其“高档社区”的总容量。

输入格式

第一行输入两个整数 N, M，表示最终共有 N 座城镇，每座城镇有 M 个蚁丘。

第二行输入 M 个整数 A1..AM，表示 1 号城镇各个蚁丘的容量。

接下来 N-1 行，每行输入 6 个整数：P, X, Y, V, Z, T，描述新城建立过程。

设当前全局变量 S 初始为 0，则本次建立新城时：

保证对每次建立的城镇都有 L <= R 且 i <= j。

新城由编号为 P 的城镇分裂而来。除区间 [L,R] 内统一加上 V 之外，其余蚁丘容量与城镇 P 对应蚁丘相同。

建城完成后，更新：

• S = 该新城中编号从 i 到 j 的蚁丘容量之和。

然后继续处理下一座新城。

输出格式

对于每一座新建城镇，输出一行一个整数，即其“高档社区”的总容量 S。

数据范围

• 1 <= N,M <= 100000
• 0 <= Ai,V <= 100000
• 0 <= X,Y,Z,T < M
• 1 <= L <= R <= M
• 1 <= i <= j <= M

样例

输入

4 4
3 6 7 5
1 2 3 1 0 1
2 1 2 6 2 2
1 0 2 8 0 3

输出

9
12
45

样例解释

最终会有 4 座城镇，每座城镇有 4 个蚁丘。

• 1 号城镇容量为 {3,6,7,5}。
• 建立 2 号城镇时，S=0，可算得 L=3,R=4,V=1,i=1,j=2，故 2 号城镇容量为 {3,6,8,6}，高档社区容量为 3+6=9，于是更新 S=9。
• 建立 3 号城镇时，S=9，它由 2 号城镇分裂而来。可算得 L=3,R=4,V=6,i=4,j=4，因此 3 号城镇容量为 {3,6,14,12}，高档社区容量为 12，更新 S=12。
• 建立 4 号城镇时，S=12，它由 1 号城镇分裂而来。可算得 L=1,R=3,V=8,i=1,j=4，因此 4 号城镇容量为 {11,14,15,5}，高档社区容量为 45。

评分说明

• 10% 数据：N,M <= 1000
• 30% 数据：每个新城都由上一个刚建立的城镇分裂而来