Trie

#include <iostream>
#include <cstdio>
#define task ""
using namespace std;
using ll = long long;
using ld = long double;

const int N = 2e5 + 2;
struct Trie{
    Trie *child[2];
    int st = 0;
    Trie() {child[0] = child[1] = NULL;}
    void Add(int id, int lim, ll &x, int val){
        if(id == lim){
            st += val;
            return;
        }
        if(!child[(x >> id) & 1])
            child[(x >> id) & 1] = new Trie;
        child[(x >> id) & 1] -> Add(id - 1, lim, x, val);
        if(child[(x >> id) & 1] -> st == 0){
            delete child[(x >> id) & 1];
            child[(x >> id) & 1] = NULL;
        }
        st += val;
    }
    int lower(int id, int lim, ll &x){
        if(id == lim)
            return st;
        int ans = 0;
        if((x >> id) & 1){
            if(child[(x >> id) & 1])
                ans += child[(x >> id) & 1] -> lower(id - 1, lim, x);
        }
        else{
            if(child[(x >> id) & 1])
                ans += child[(x >> id) & 1] -> lower(id - 1, lim, x);
            if(child[!((x >> id) & 1)])
                ans += child[!((x >> id) & 1)] -> st;
        }
        return ans;
    }
    int cnt(int id, int lim, ll &x){
        if(id == lim)
            return st;
        if(child[(x >> id) & 1])
            return child[(x >> id) & 1] -> cnt(id - 1, lim, x);
        return 0;
    }
};

const ll mod = 1e9 + 1;
int n, q;
ll a[N];
ll lst(0);
Trie beg;

void Read(){
    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> a[i],
        beg.Add(60, -1, a[i], 1);
}

void Solve(){
    cin >> q;
    while(q--){
        //cerr << q << "\n";
        int type;
        cin >> type;
        if(type == 1){
            int x; ll y;
            cin >> x >> y;
            x = (x + lst) % n;
            ll t = (y + (ll)lst) % mod;
            beg.Add(60, -1, a[x], -1);
            beg.Add(60, -1, t, 1);
            a[x] = t;
        }
        else{
            ll x, y;
            cin >> x >> y;
            int u = beg.lower(60, -1, x),
                v = beg.lower(60, -1, y),
                t = beg.cnt(60, -1, y);
            //cout << u << " " << v << " " << t << "\n";
            lst = u - v + t;
            cout << lst << "\n";
        }
    }
}

main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0); if(fopen(task".INP", "r"))
    freopen(task".INP", "r", stdin),
    freopen(task".OUT", "w", stdout);
    Read();
    Solve();
}