<Segment Trees with Lazy> TEMPLATE

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define mp make_pair
#define pb push_back
#define pii pair <int, int>
#define piii pair<pii, int>
#define vi vector<int>
#define vpii vector<pii>

#define read1(a) int a; scanf("%d", &a)
#define read2(a, b) int a, b; scanf("%d %d", &a, &b)
#define read3(a, b, c) int a, b, c; scanf("%d %d %d", &a, &b, &c)

#define FOR(i, a, b) for (int i=a; i<b; i++)
#define F0R(i, a) for (int i=0; i<a; i++)

#define readgi(n) F0R(i, n) { scanf("%d", &arr[i]); }
#define readgs(n) F0R(i, n) { scanf(" %c", &arr[i]); }

#define f first
#define s second

#define usaco(in, out) freopen(in, "r", stdin); freopen(out, "w", stdout);

#define println1(a) printf("%d\n", a);
#define println2(a, b) printf("%d %d\n", a, b);
#define println3(a, b, c) printf("%d %d %d\n", a, b, c);
#define pv(v) for (int i : v) { printf("%d ", i); } printf("\n");

const int MOD = 1000000007;
const int MAX = 100005;

int arr[4*MAX];
int lzy[4*MAX];
int tree[4*MAX];
int sze[4*MAX];

void push(int n) {
    if (!lzy[n]) { return; }
    tree[n] += sze[n] * lzy[n];
    lzy[2*n] += lzy[n]; lzy[2*n+1] += lzy[n];
    lzy[n] = 0;
}

void build(int n, int a, int b) {
    if (a == b) { sze[n] = 1; tree[n] = arr[a]; return; }
    build(2*n, a, (a+b)/2);
    build(2*n+1, (a+b)/2+1, b);
    tree[n] = tree[2*n] + tree[2*n+1];
    sze[n] = sze[2*n] + sze[2*n+1];
}

void update(int n, int a, int b, int i, int j, int v) {
    push(n);
    if (a>j || b<i) { return; }
    if (i<=a && b<=j) { lzy[n] += v; push(n); return; }
    update(2*n, a, (a+b)/2, i, j, v);
    update(2*n+1, (a+b)/2+1, b, i, j, v);
    tree[n] = tree[2*n] + tree[2*n+1];
}

int query(int n, int a, int b, int i, int j) {
    push(n);
    if (a>j || b<i) { return 0; }
    if (i<=a && b<=j) { return tree[n]; }
    return query(2*n, a, (a+b)/2, i, j) + query(2*n+1, (a+b)/2+1, b, i, j);
}

int main() {

}