Pro found a book about algorithms in the library. The book introduces a data structure called a "Segment Tree."

• A segment tree is a rooted binary tree where each node corresponds to an interval $[l, r]$ on a sequence, with the root node corresponding to $[1, n]$.
• For each node, if the sequence interval $[l, r]$ it represents satisfies $l = r$, it is a leaf node; otherwise, there exists an integer $k$ ($l \le k < r$) such that its left child represents the interval $[l, k]$ and its right child represents the interval $[k + 1, r]$. To ensure time complexity, $k$ is typically taken as $\lfloor (l + r) / 2 \rfloor$.
• Segment trees can perform operations such as point updates, range updates, and range queries. The implementation of range update operations usually requires maintaining additional information called lazy tags.

After briefly understanding how a segment tree maintains range additions, Pro wanted to implement a segment tree that supports range additions. He wrote the following code:

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

(Other parts are omitted; all variables in the code are of type unsigned)

To verify the correctness of this code, Pro constructed a segment tree for a sequence of length $n$ and set two additional weights, $va_i$ and $vb_i$, on each node. Next, he performed $m$ range addition operations on the segment tree and output the return value of the following function after each operation:

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

Because Dr. K's computer was so fast, Pro's code produced the result in just 1ms. However, he still doesn't know if the code is correct, so please calculate the result of the function above and compare it with the result Pro obtained.

Input

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

The next $2n - 1$ lines each describe a node. The $i$-th line starts with four integers $l_i, r_i, va_i, vb_i$, representing the left and right endpoints of the interval corresponding to the $i$-th node in the segment tree, as well as the two additional weights on the node. If the node is not a leaf node, two additional integers $lc_i$ and $rc_i$ follow, representing the indices of the left and right children of this node.

The next $m$ lines each contain three integers $ql, qr, k$, representing the left endpoint, right endpoint, and the value to be added for a range addition operation.

Output

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

Examples

Input 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

Output 1

45
74
76
154

Input 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

Output 2

36
82
106
155

Input 3

See ex_data3.in in the additional files.

Output 3

See ex_data3.ans in the additional files.

Input 4

See ex_data4.in in the additional files.

Output 4

See ex_data4.ans in the additional files.

Input 5

See ex_data5.in in the additional files.

Output 5

See ex_data5.ans in the additional files.

Constraints

If the test case ID $\text{mod} \ 5$ is $2$ or $3$, it is guaranteed that $va_i = 0$.

If the test case ID $\text{mod} \ 5$ is $4$ or $0$, it is guaranteed that $vb_i = 0$.

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

The input size for this problem is large; please use fast I/O methods.