#include<bits/stdc++.h>
using namespace std;
using lol=long long int;
#define endl "\n"
const lol mod1=1e9+7,mod2=998244353,mod3=100000000000000003,hashpr=31;
const lol inf=9e18+8;
const double eps=1e-12;
const double PI=acos(-1.0);
const int N=1e5+5;
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;
using ordered_set_type=lol;
typedef tree<ordered_set_type,null_type,less<ordered_set_type>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

pair<lol,lol> exgcd(lol a,lol b){
    if(b == 0){
        return make_pair(1, 0);
    }
    auto [x1, y1] = exgcd(b, a % b);
    lol x = y1;
    lol y = x1 - y1 * (a / b);
    return make_pair(x, y);
}

struct LinearBasis{
    static const int d = 65;
    lol mod;
    struct Vector{
        lol mod;
        vector<lol> vec;
        Vector(lol v, lol m):mod(m){
            vec.resize(d, 0);
            vector<lol> t;
            while(v){
                t.push_back(v % mod);
                v /= mod;
            }
            for(int i=0;i<(int)t.size();i++){
                vec[d-1-i] = t[i];
            }
        }
        lol to_number(){
            lol R = 0;
            for(int i=0;i<d;i++){
                R = mod * R + vec[i];
            }
            return R;
        }
        lol operator[](int p){return vec[p];}
        const lol operator[](int p) const{return vec[p];}
        Vector& operator+=(const Vector& other){
            for(int i=0;i<d;i++){
                this->vec[i] += other.vec[i] % mod;
                this->vec[i] %= mod;
            }
            return *this;
        }
        friend Vector operator+(Vector lhs, const Vector& rhs){
            lhs += rhs;
            return lhs;
        }
        Vector& operator-=(const Vector& other){
            for(int i=0;i<d;i++){
                this->vec[i] -= other.vec[i] % mod;
                this->vec[i] = (this->vec[i] + mod) % mod;
            }
            return *this;
        }
        friend Vector operator-(Vector lhs, const Vector& rhs){
            lhs -= rhs;
            return lhs;
        }
        Vector& operator*=(const lol& scalar){
            for(int i=0;i<d;i++){
                this->vec[i] *= scalar % mod;
                this->vec[i] %= mod;
            }
            return *this;
        }
        friend Vector operator*(Vector lhs, const lol& rhs){
            lhs *= rhs;
            return lhs;
        }
        friend Vector operator*(const lol& rhs, Vector lhs){
            lhs *= rhs;
            return lhs;
        }
    };
    vector<Vector> A;   //this is the basis
    Vector vec(lol v){
        return Vector(v, mod);
    }
    LinearBasis(lol m): mod(m){A.resize(d,vec(0));}
    void add(Vector V){
        for(int i=0;i<d;i++){
            if(V[i] != 0){
                if(A[i][i] == 0){
                    auto [s,t] = exgcd(V[i], mod);
                    s = (s % mod + mod)%mod;
                    t = (t % mod + mod)%mod;
                    A[i] = V * s;
                    V = V * (mod / A[i][i]);
                }else if(V[i] % A[i][i] == 0){
                    V -= A[i] * (V[i] / A[i][i]);
                }else{
                    auto W = A[i];
                    auto [s,t] = exgcd(V[i], W[i]);
                    s = (s % mod + mod)%mod;
                    t = (t % mod + mod)%mod;
                    A[i] = V * s + W * t;
                    V -= A[i] * (V[i] / A[i][i]);
                    W -= A[i] * (W[i] / A[i][i]);
                    add(W);
                }
            }
        }
    }
    lol total(){
        lol B = 1;
        for(int i=0;i<d;i++){
            if(A[i][i]) B *= mod / A[i][i];
        }
        return B;
    }
    lol kth(lol k){
        lol B = total();
        if(k > B)   return -1;
        auto R = vec(0);
        for(int i=0;i<d;i++){
            if(!A[i][i])    continue;
            B /= mod / A[i][i];
            lol l = min((k - 1) / B, mod / A[i][i] - 1);
            lol q = (R[i] / A[i][i]) % (mod / A[i][i]);
            q = (l - q + mod / A[i][i]) % (mod / A[i][i]);
            k -= l * B;
            R += A[i] * q;
        }
        return R.to_number();
    }
};

void solve(){
    lol k;
    int q;
    cin>>k>>q;
    auto L = LinearBasis(k);
    while(q--){
        int t;
        lol x;
        cin>>t>>x;
        if(t==1){
            L.add(L.vec(x));
        }else if(t==2){
            cout<<L.kth(x)<<endl;
        }else{
            // You can find the kth smallest number
            lol l = 1, r = L.total(), mid, ans;
            while(l<=r){
                mid = l + (r - l) / 2;
                if(L.kth(mid) <= x){
                    l = mid + 1;
                    ans = mid;
                }else{
                    r = mid - 1;
                }
            }
            cout<<ans<<endl;
        }
    }
}

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int _=1;
// cin>>_;
while(_--)
{
    solve();
}
return 0;
}