Problem Description

Plo found a book about algorithms in the library. The book introduced a data structure called a “segment tree”.

A segment tree is a rooted binary tree. Each node corresponds to an interval $[l,r]$ on a sequence, and the root corresponds to $[1,n]$.

For each node, if its interval $[l,r]$ satisfies $l=r$, then it is a leaf node. Otherwise, there exists an integer $k(l\le k<r)$ such that its left child represents $[l,k]$ and its right child represents $[k+1,r]$. To guarantee time complexity, $k$ is usually chosen as $\left\lfloor\frac{l+r}{2}\right\rfloor$.

A segment tree can support operations such as point update, range update, and range query. Implementing range updates usually requires maintaining extra information called “lazy tags”.

After learning how a segment tree maintains range add, Plo wanted to implement a segment tree that supports range add. So he wrote the following code:

#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;
}

To test whether this code is correct, Plo built a segment tree that maintains a sequence of length $n$, and set two extra weights $va_i, vb_i$ on each node. Then he performed $m$ range add operations on the segment tree, and after each range add operation, he printed the return value of the following function.

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

Because Dr. K’s computer was extremely fast, Plo’s code produced results in just 1 ms. However, he still did not know whether the code was correct, so please compute the result of the function above and compare it with the result obtained by Plo.

Input Format

The first line contains two integers $n,m$, representing the sequence length maintained by the segment tree and the number of operations.

The next $2n-1$ lines describe the segment tree. On line $i$, there are first four integers $l_i, r_i, va_i, vb_i$, representing the left endpoint and right endpoint of the interval corresponding to node $i$ on the segment tree, as well as the two extra weights on this node. If this node is not the root, then there are two more integers $lc_i, rc_i$, representing the indices of its left child and right child.

The next $m$ lines each contain three integers $ql_i, qr_i, k_i$, representing the left endpoint, right endpoint, and the value added in one range add operation.

Output Format

After each range add operation, output one line with one positive integer representing the return value of the foobar function.

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

Hint

【Scale and Conventions】

If the test point ID $\bmod 5$ is $2$ or $3$, then for that test point it is guaranteed that $va_i=0$.

If the test point ID $\bmod 5$ is $4$ or $0$, then for that test point it is guaranteed that $vb_i=0$.

For $100\%$ of the data, it is guaranteed that $1\le n,q\le2\times10^5$. The given segment tree and range add operations are valid, and $0\le va_i,vb_i,k_i<2^{32}$.

Translated by ChatGPT 5