LAZY ST, += on [l,r] , get_segment

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    int T;
    cin >> T;
    struct Node {
        int lazy = 0;
        int val = 0;
    };
    auto relax = [&] (vector<Node>& tree, int u, int tl, int tr) -> void {
        int tm = (tl + tr) >> 1;
        int szl = tm-tl+1;
        int szr = tr-(tm+1)+1;
        tree[2*u+1].lazy += tree[u].lazy;
        tree[2*u+1].val += tree[u].lazy*szl;
        tree[2*u+2].lazy += tree[u].lazy;
        tree[2*u+2].val += tree[u].lazy*szr;
        tree[u].lazy = 0;
    };
    auto inc = [&] (auto f, vector<Node>& tree, int u, int tl, int tr, int l, int r, int val) -> void {
        if (tl == l && tr == r) {
            tree[u].val += val*(tr-tl+1);
            tree[u].lazy += val;
            return;
        }
        relax(tree, u, tl, tr);
        int tm = (tl + tr) >> 1;
        if (l <= tm) {
            f(f, tree, 2*u+1, tl, tm, l, min(r, tm), val);
        }
        if (r >= tm+1) {
            f(f, tree, 2*u+2, tm+1, tr, max(l, tm+1), r, val);
        }
        tree[u].val = tree[2*u+1].val + tree[2*u+2].val;
    };
    auto gt = [&] (auto f, vector<Node>& tree, int u, int tl, int tr, int l, int r) -> int {
        if (tl == l && tr == r) {
            return tree[u].val;
        }
        relax(tree, u, tl, tr);
        int tm = (tl + tr) >> 1;
        int ret = 0;
        if (l <= tm) {
            ret += f(f, tree, 2*u+1, tl, tm, l, min(r, tm));
        }
        if (r >= tm+1) {
            ret += f(f, tree, 2*u+2, tm+1, tr, max(l, tm+1), r);
        }
        return ret;
    };
    vector<Node> ST(3'000'000);
    for (int tt = 0; tt < T; tt += 1) {
        int n;
        cin >> n;
        fill(ST.begin(), ST.begin()+4*n+10, Node{});
        inc(inc, ST, 0, 1, n, 1, 3, 5);
        int q;
        cin >> q;
        for (int i = 0; i < q; i += 1) {
//            int tp;
//            cin >> tp;
//            if (tp == 1) {
//
//            }
            int l, r;
            cin >> l >> r;
            cout << gt(gt, ST, 0, 1, n, l, r) << "\n";
        }
    }
}