rt

using i64 = long long;

const int maxn = 114514;

int a[maxn];
i64 tag[4 * maxn];
i64 tr[4 * maxn];

auto bf = [](auto x, auto y) { return x + y; };
void apply(int u, int l, int r, int x) {
	tr[u] += i64(r - l + 1) * x;
	tag[u] += x;
}

void build(int u, int l, int r) {
    if (l == r) {
        tr[u] = a[l];
        return ;
    }
    int mid = (l + r) >> 1;
    build(u * 2, l, mid);
    build(u * 2 + 1, mid + 1, r);
    tr[u] = bf(tr[u * 2], tr[u * 2 + 1]);
}

void pushdown(int u, int l, int r) {
    if (tag[u]) {
        int mid = (l + r) >> 1;
        apply(u * 2, l, mid, tag[u]);
        apply(u * 2 + 1, mid + 1, r, tag[u]);
        tag[u] = 0;
    }
}

void update(int u, int l, int r, int s, int t, int x) {
    if (s <= l && r <= t) {
        apply(u, l, r, x);
        return ;
    }
    pushdown(u, l, r);
    int mid = (l + r) >> 1;
    if (s <= mid) update(u * 2, l, mid, s, t, x);
    if (t > mid) update(u * 2 + 1, mid + 1, r, s, t, x);
    tr[u] = bf(tr[u * 2], tr[u * 2 + 1]);
}

i64 query(int u, int l, int r, int s, int t) {
    if (s <= l && r <= t) return tr[u];
    pushdown(u, l, r);
    int mid = (l + r) >> 1;
    if (t <= mid) return query(u * 2, l, mid, s, t);
    if (s > mid) return query(u * 2 + 1, mid + 1, r, s, t);
    return bf(query(u * 2, l, mid, s, t), query(u * 2 + 1, mid + 1, r, s, t));
}