// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#define dibs reserve
#define OVER9000 1234567890
#define tisic 47
#define soclose 10e-7
// mylittlepony
using namespace std;

struct IT {
    // uses [a,b) intervals
    struct node {
        int zac,kon,val;
        int son[2];}
    n0; // null node
    vector<node> T; // dat structure

    void constT(int akt) { // construct interval tree with root akt
        node n =T[akt];
        if(n.zac+1 == n.kon) return; // this node is leaf, interval [a,a)
        // split the interval in half, construct subtrees for each half
        for(int i =0; i < 2; i++) {
            T[akt].son[i] =T.size();
            if(i == 0) n.kon =(T[akt].zac+T[akt].kon)/2;
            else {
                n.zac =n.kon;
                n.kon =T[akt].kon;}
            T.push_back(n);
            constT(T[akt].son[i]);}
        }

    IT(int N) { // constructor; T is the interval [0,N)
        n0.zac =n0.val =0;
        n0.kon =N;
        n0.son[0] =n0.son[1] =-1;
        T.push_back(n0);
        constT(0);}

    int get(int akt, int pos) { // get value at position pos
        node n =T[akt];
        if(n.zac == pos && n.kon == pos+1) return n.val; // leaf corresponding to pos
        if((n.zac+n.kon)/2 > pos) return get(n.son[0],pos); // pos is in left half
        else return get(n.son[1],pos);} // pos is in right half

    void add(int akt, int pos, int v) { // value[pos] +=v
        node n =T[akt];
        T[akt].val +=v;
        if(zac+1 == kon) return; // leaf, can't go any deeper
        // move to the half-interval containing position pos, update it
        if((n.zac+n.kon)/2 > pos) add(n.son[0],pos,v); // it's the left one
        else add(n.son[1],pos,v);}; // it's the right one
        
// look at my code
// my code is amazing