#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

#define mp make_pair
#define pb push_back
#define pii pair<int, int>

map<ll, ll> lft, rgt;
map<ll, ll> val;

ll qry(ll l, ll r){
    if(val.find(r) == val.end()) return r;
    auto it = rgt.upper_bound(r);
    if(rgt.find(r) != rgt.end()) it = rgt.find(r);
    if(it -> second <= l) return 0;
    return (it -> second - 1);
}

void clear(){
    val.clear();
    lft.clear();
    rgt.clear();
}

void update(int x){
    if(val.find(x) != val.end()) return;
    val[x] = 0;
    if(rgt.find(x-1) != rgt.end()){
        ll l = rgt[x-1];
        rgt.erase(rgt.find(x-1));
        rgt[x] = l;
    }else{
        rgt[x] = x;
    }
    auto it = rgt.upper_bound(x);
    if(it != rgt.end()){
        ll l = it -> second;
        if(l == x+1){
            ll r = it -> first;
            ll _l = rgt[x];
            rgt.erase(rgt.find(x));
            rgt[r] = _l;
        }
    }
}

void print(){
    for(auto i :rgt ) cout << "(" << i.first << " " << i.second << ") "; cout << endl;
}

int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    
    int t;
    cin >> t;
    while(t--){
        clear();
        ll n, q, s = 0;
        cin >> n >> q;
        while(q--){
            int ty;
            cin >> ty;
            if(ty == 1){
                ll x;
                cin >> x;
                //x += s;
                update(x);
                //cout << x << endl;
            }else{
                ll l, r;
                cin >> l >> r;
                //l += s, r += s;
                ll ans = qry(l, r);
                s = (s  + ans) % n;
                cout << ans << '\n';
            }
           // print();
        }
    }
    return 0;
}