### Фенвик с прибавлением на отрезке

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define long ll
#define all(x) begin(x), end(x)

struct Range_fenwick {
    static const int N = 1e6;
    long k[N];
    long b[N];

    void internal_add(int i, long dk, long db) {
        for (; i < N; i |= i + 1) {
            k[i] += dk;
            b[i] += db;
        }
    }

    long internal_sum(int i) {
        int pos = i;
        long sum_k = 0, sum_b = 0;
        for (; i >= 0; i = (i & (i + 1)) - 1) {
            sum_k += k[i];
            sum_b += b[i];
        }
        return pos * sum_k + sum_b;
    }

    void add(int l, int r, long d) {
        internal_add(l, d, -(l - 1) * d);
        internal_add(r + 1, -d, r * d);
    }

    long sum(int l, int r) {
        return internal_sum(r) - internal_sum(l - 1);
    }
};

Range_fenwick tree;

int main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
#endif
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    return 0;
}