题目描述

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

• 线段树是一种有根的二叉树，其每个节点对应了序列上的一个区间 $[l, r]$，其中根节点对应 $[1, n]$。
• 对于每个节点，若其代表的序列区间 $[l, r]$ 满足 $l = r$，则其为叶节点；否则存在整数 $k$（$l \le k < r$），满足其左儿子代表区间 $[l, k]$，右儿子代表区间 $[k + 1, r]$。为了保证其时间复杂度，$k$ 一般会取 $\lfloor (l + r) / 2 \rfloor$。
• 线段树可以实现单点修改，区间修改，区间查询等操作。其中区间修改操作的实现通常需要维护名为懒惰标记的额外信息。

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

#define len(i) (r[i]-l[i]+1)
void push_down(unsigned 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(unsigned i, unsigned ql, unsigned 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;
}

（省略了其他部分，代码中所有变量均为 unsigned 类型）

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

unsigned foobar() {
    unsigned tot = 0;
    for (unsigned 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, qr, k$，表示一次区间加操作的左端点，右端点和增加的值。

输出格式

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

样例输入 1

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

样例输出 1

45
74
76
154

样例输入 2

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

样例输出 2

45
74
76
154

样例输入 3

见附加文件中的 ex_data3.in。

样例输出 3

见附加文件中的 ex_data3.ans。

样例输入 4

见附加文件中的 ex_data4.in.

样例输出 4

见附加文件中的 ex_data4.ans.

样例输入 5

见附加文件中的 ex_data5.in.

样例输出 5

见附加文件中的 ex_data5.ans.

数据范围

如果测试点编号 $\text{mod} , 5$ 为 $2$ 或 $3$，该测试点保证 $va_i = 0$。

如果测试点编号 $\text{mod} , 5$ 为 $4$ 或 $0$，该测试点保证 $vb_i = 0$。

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

本题输入量较大，请使用较快的输入方式。