STI

#include <bits/stdc++.h>
#define MAX 100007

using namespace std;

struct node{
    int val, acum;
    node *l, *r;

    node(){
        val = acum = 0;
        l = r = NULL;
    }
} *root;

void add(node* no,int l, int r, int v){
    no->val += (r-l+1)*v;
    no->acum += v;
}

void update(node* no, int l, int r, int x, int y, int v){
    if(r < x || y < l) return;
    else if(x <= l && r <= y) add(no, l, r,  v);
    else{
        int mid = (l+r)/2;

        no->l = (no->l == NULL)? new node(): no->l;
        no->r = (no->r == NULL)? new node(): no->r;
        add(no->l, l, mid, no->acum);
        add(no->r, mid+1, r,no->acum);
        no->acum = 0;

        update(no->l, l, mid, x, y, v);
        update(no->r, mid+1, r, x, y, v);

        no->val = no->l->val + no->r->val;
    }
}

int query(node* no, int l, int r, int x, int y){
    if(r < x || y < l) return 0;
    else if(x <= l && r <= y) return no->val;
    else{
        int mid = (l+r)/2;

        no->l = (no->l == NULL)? new node(): no->l;
        no->r = (no->r == NULL)? new node(): no->r;
        add(no->l, l, mid, no->acum);
        add(no->r, mid+1, r,no->acum);
        no->acum = 0;

        return query(no->l, l, mid, x, y) +
               query(no->r, mid+1, r, x, y);

    }
}
int main(){
    return 0;
}