Power of three

    const int mod = 3;
    vector<int> tree;
    void build(vector<int> &a,int v,int l,int r){
        if(l==r)
            tree[v] = a[l];
        else{
            int mid = (l+r)/2;
            build(a,2*v,l,mid);
            build(a,2*v+1,mid+1,r);
            tree[v] = (tree[2*v]+tree[2*v+1])%3;
        }
    }
    int range_sum(int v,int tl,int tr,int l,int r){
        if(l>r)
            return 0;
        if(l==tl and r==tr)
            return tree[v];
        int tm = (tl+tr)/2;
        return (range_sum(2*v,tl,tm,l,min(tm,r))+range_sum(2*v+1,tm+1,tr,max(l,tm+1),r))%3;
    }
    void update(int v,int tl,int tr,int idx,int val){
        if(tl == tr)
            tree[v] = val;
        else{
            int tm = (tl+tr)/2;
            if(idx<=tm)
                update(2*v,tl,tm,idx,val);
            else
                update(2*v+1,tm+1,tr,idx,val);
            tree[v] = (tree[2*v]+tree[2*v+1])%3;
        }
    }
    vector<int> Solution::solve(string s, vector<vector<int> > &queries) {
        const int n = s.size();
        tree.assign(4*n,0);
        vector<int> power(n);
        vector<int> a(n);
        power[0] = 1;
        for(int i=1;i<n;i++){
            power[i] = (power[i-1]*2)%mod;
        }
        reverse(power.begin(),power.end());
        for(int i=0;i<n;i++){
            if(s[i]=='1')
                a[i] = power[i];
        }

        build(a,1,0,n-1);
        vector<int> ans;
        for(auto &q:queries){
            int x = q[0],u = q[1]-1,v = q[2]-1;
            if(x){
                if(s[u]=='0'){
                    s[u] = '1';
                    a[u] = power[u];
                    update(1,0,n-1,u,power[u]);
                }
                ans.push_back(-1);
            }else{
                int curr = range_sum(1,0,n-1,u,v);
                ans.push_back((curr*power[v])%3);
            }
        }
        return ans;
    }