template<typename T>
struct BIT{
    int n;
    vector<T>t;
    BIT(int m):n(m),t(m+1,0){}
    void ins(int x,int k){if(!x)return;for(;x<=n;x+=x&-x)t[x]+=k;}
    int ask(int x){int z=0;for(;x;x^=x&-x)z+=t[x];return z;}
    int ask(int l,int r){return ask(r)-ask(l-1);}
};