题目描述

普罗在图书馆找到了一本关于算法的书。书中介绍了一种名为“线段树”的数据结构。

线段树是一种有根的二叉树，其每个节点对应了序列上的一个区间 $[l,r]$，其中根节点对应 $[1,n]$。

对于每个节点，若其代表的序列区间 $[l,r]$ 满足 $l=r$，则其为叶节点；否则存在整数 $k(l\le k<r)$，满足其左儿子代表区间 $[l,k]$，右儿子代表区间 $[k+1, r]$。为了保证其时间复杂度，$k$ 一般会取 $\left\lfloor\frac{l+r}{2}\right\rfloor$。

线段树可以实现单点修改，区间修改，区间查询等操作。其中区间修改操作的实现通常需要维护名为懒惰标记的额外信息。

在简单了解了线段树如何维护区间加之后，普罗想要实现一个维护区间加的线段树。于是他写下了如下的代码：

#define len(i) (r[i]-l[i]+1)
void push_down(int i)
{
    a[lc[i]]+=len(lc[i])*lz[i];
    lz[lc[i]]+=lz[i];
    a[rc[i]]+=len(rc[i])*lz[i];
    lz[rc[i]]+=lz[i];
    lz[i]=0;
    return;
}
void add(int i,int ql,int qr,unsigned k)
{
    if(qr<l[i]||r[i]<ql) return;
    if(ql<=l[i]&&r[i]<=qr){
        a[i]+=len(i)*k;
        lz[i]+=k;
        return;
    }
    push_down(i);
    add(lc[i],ql,qr,k);
    add(rc[i],ql,qr,k);
    a[i]=a[lc[i]]+a[rc[i]];
    return;
}

为了检验这份代码的正确性，普罗构建了一个维护的序列长为 $n$ 的线段树，并在每个节点上设置两个额外的权值 $va_i,vb_i$，接下来他在线段树上进行了 $m$ 次区间加的操作，在每次区间加操作后输出了下面函数的返回值。

unsigned foobar(){
	unsigned tot=0;
	for(int i=1;i<2*n;i++)tot+=va[i]*a[i]+vb[i]*lz[i];
	return tot;
}

因为 K 博士的电脑实在太快了，普罗的代码只花了 1ms 就得出了结果。但是他还是不知道代码是不是正确的，所以请你计算出上面的函数的结果和普罗得出的结果比较吧。

输入格式

第一行两个整数 $n,m$，表示线段树维护的序列长度和操作次数。

接下来 $2n-1$ 行，第 $i$ 行首先是四个整数 $l_i,r_i,va_i,vb_i$，表示线段树上第 $i$ 个节点对应的区间的左端点和右端点，以及节点上的两个额外权值。如果这个节点不是根节点，那么接下来还有两个整数 $lc_i,rc_i$，表示这个节点的左儿子编号和右儿子编号。

接下来 $m$ 行，每行三个整数 $ql_i,qr_i,k_i$，表示一次区间加操作的左端点，右端点和增加的值。

输出格式

在每次区间加操作后输出一行一个正整数表示 foobar 函数的返回值。

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

45
74
76
154

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

36
82
106
155

提示

【数据规模与约定】

如果测试点编号 $\bmod 5$ 为 $2$ 或 $3$，该测试点保证 $va_i=0$。

如果测试点编号 $\bmod 5$ 为 $4$ 或 $5$，该测试点保证 $vb_i=0$。

对于 $100\%$ 的数据，保证 $1\le n,q\le2\times10^5$，给出的线段树和区间加操作是合法的，$0\le va_i,vb_i,k_i<2^{32}$。