#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; //#define int long long typedef long long ll; typedef unsigned long long ul; typedef unsigned int ui; //ll mod = 1; constexpr ll mod = 998244353; //constexpr ll mod = 1000000009; const int mod17 = 1000000007; const ll INF = (ll)mod17 * mod17; typedef pairP; #define rep(i,n) for(int i=0;i=0;i--) #define Rep(i,sta,n) for(int i=sta;i=1;i--) #define Rep1(i,sta,n) for(int i=sta;i<=n;i++) #define all(v) (v).begin(),(v).end() typedef pair LP; using ld = double; typedef pair LDP; const ld eps = 1e-10; const ld pi = acosl(-1.0); template void chmin(T& a, T b) { a = min(a, b); } template void chmax(T& a, T b) { a = max(a, b); } template vector vmerge(vector& a, vector& b) { vector res; int ida = 0, idb = 0; while (ida < a.size() || idb < b.size()) { if (idb == b.size()) { res.push_back(a[ida]); ida++; } else if (ida == a.size()) { res.push_back(b[idb]); idb++; } else { if (a[ida] < b[idb]) { res.push_back(a[ida]); ida++; } else { res.push_back(b[idb]); idb++; } } } return res; } template void cinarray(vector& v) { rep(i, v.size())cin >> v[i]; } template void coutarray(vector& v) { rep(i, v.size()) { if (i > 0)cout << " "; cout << v[i]; } cout << "\n"; } ll mod_pow(ll x, ll n, ll m = mod) { if (n < 0) { ll res = mod_pow(x, -n, m); return mod_pow(res, m - 2, m); } if (abs(x) >= m)x %= m; if (x < 0)x += m; //if (x == 0)return 0; ll res = 1; while (n) { if (n & 1)res = res * x % m; x = x * x % m; n >>= 1; } return res; } //mod should be <2^31 struct modint { int n; modint() :n(0) { ; } modint(ll m) { if (m < 0 || mod <= m) { m %= mod; if (m < 0)m += mod; } n = m; } operator int() { return n; } }; bool operator==(modint a, modint b) { return a.n == b.n; } bool operator<(modint a, modint b) { return a.n < b.n; } modint operator+=(modint& a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= (int)mod; return a; } modint operator-=(modint& a, modint b) { a.n -= b.n; if (a.n < 0)a.n += (int)mod; return a; } modint operator*=(modint& a, modint b) { a.n = ((ll)a.n * b.n) % mod; return a; } modint operator+(modint a, modint b) { return a += b; } modint operator-(modint a, modint b) { return a -= b; } modint operator*(modint a, modint b) { return a *= b; } modint operator^(modint a, ll n) { if (n == 0)return modint(1); modint res = (a * a) ^ (n / 2); if (n % 2)res = res * a; return res; } ll inv(ll a, ll p) { return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p); } modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); } modint operator/=(modint& a, modint b) { a = a / b; return a; } const int max_n = 1 << 20; modint fact[max_n], factinv[max_n]; void init_f() { fact[0] = modint(1); for (int i = 0; i < max_n - 1; i++) { fact[i + 1] = fact[i] * modint(i + 1); } factinv[max_n - 1] = modint(1) / fact[max_n - 1]; for (int i = max_n - 2; i >= 0; i--) { factinv[i] = factinv[i + 1] * modint(i + 1); } } modint comb(int a, int b) { if (a < 0 || b < 0 || a < b)return 0; return fact[a] * factinv[b] * factinv[a - b]; } modint combP(int a, int b) { if (a < 0 || b < 0 || a < b)return 0; return fact[a] * factinv[a - b]; } ll gcd(ll a, ll b) { a = abs(a); b = abs(b); if (a < b)swap(a, b); while (b) { ll r = a % b; a = b; b = r; } return a; } template void addv(vector& v, int loc, T val) { if (loc >= v.size())v.resize(loc + 1, 0); v[loc] += val; } /*const int mn = 2000005; bool isp[mn]; vector ps; void init() { fill(isp + 2, isp + mn, true); for (int i = 2; i < mn; i++) { if (!isp[i])continue; ps.push_back(i); for (int j = 2 * i; j < mn; j += i) { isp[j] = false; } } }*/ //[,val) template auto prev_itr(set& st, T val) { auto res = st.lower_bound(val); if (res == st.begin())return st.end(); res--; return res; } //[val,) template auto next_itr(set& st, T val) { auto res = st.lower_bound(val); return res; } using mP = pair; mP operator+(mP a, mP b) { return { a.first + b.first,a.second + b.second }; } mP operator+=(mP& a, mP b) { a = a + b; return a; } mP operator-(mP a, mP b) { return { a.first - b.first,a.second - b.second }; } mP operator-=(mP& a, mP b) { a = a - b; return a; } LP operator+(LP a, LP b) { return { a.first + b.first,a.second + b.second }; } LP operator+=(LP& a, LP b) { a = a + b; return a; } LP operator-(LP a, LP b) { return { a.first - b.first,a.second - b.second }; } LP operator-=(LP& a, LP b) { a = a - b; return a; } mt19937 mt(time(0)); const string drul = "DRUL"; string senw = "SENW"; //DRUL,or SENW //int dx[4] = { 1,0,-1,0 }; //int dy[4] = { 0,1,0,-1 }; //------------------------------------ //x,yがax+by=gcd(a,b)の解になる ll extgcd(ll a, ll b, ll& x, ll& y) { ll d = a; if (b != 0) { d = extgcd(b, a % b, y, x); y -= (a / b) * x; } else { x = 1; y = 0; } return d; } //aのmod mでの逆元を求める ll mod_inverse(ll a, ll m) { ll x, y; extgcd(a, m, x, y); return (m + x % m) % m; } void solve() { int b, q; cin >> b >> q; int sz = 0; { ll t = 1; while (t < mod17) { t *= b; sz++; } } ll sup = 1; { ll t = 1; rep(i, sz) { sup += t * (b - 1); t *= b; } sup++; } vector> bs; vector> lateradds; auto addlater = [&](vector v) { lateradds.push_back(v); rep(j, v.size()) { if (v[j] != 0) { ll g = gcd(v[j], b); vector nv = v; rep(i, nv.size()) { nv[i] *= b / g; nv[i] %= b; } lateradds.push_back(nv); } } }; auto add_ = [&](vector v) { int id = 0; int idv = 0; vector> rads; rep(i, bs.size()) { while (bs[i][id] == 0)id++; while (idv < v.size() && v[idv] == 0)idv++; if (idv == v.size())return; if (idv < id) { //modify v ll g = gcd(b, v[idv]); ll x = mod_inverse(v[idv] / g, b / g); rep(j, v.size()) { (v[j] *= x) %= b; } assert(v[idv] == g); bs.insert(bs.begin() + i, v); addlater(v); return; } else if (idv == id) { { //modify v ll g = gcd(b, v[idv]); ll x = mod_inverse(v[idv] / g, b / g); rep(j, v.size()) { (v[j] *= x) %= b; } } ll g = gcd(bs[i][id], v[idv]); assert(b % g == 0); if (g != bs[i][id]) { ll x, y; extgcd(bs[i][id], v[idv], x, y); x %= b; y %= b; //cout << "?? " << x << " " << y << "\n"; vector nv(sz); rep(j, nv.size()) { nv[j] = bs[i][j] * x + v[j] * y; nv[j] %= b; if (nv[j] < 0)nv[j] += b; } assert(nv[id] == g); swap(bs[i], nv); addlater(nv); addlater(bs[i]); } assert(bs[i][id] == g); ll coef = v[idv] / g; Rep(j, idv, sz) { v[j] -= coef * bs[i][j]; v[j] %= b; if (v[j] < 0)v[j] += b; } addlater(v); return; } } while (idv < v.size() && v[idv] == 0)idv++; if (idv != v.size()) { //modify v ll g = gcd(b, v[idv]); ll x = mod_inverse(v[idv] / g, b / g); rep(j, v.size()) { (v[j] *= x) %= b; } assert(v[idv] == g); bs.push_back(v); addlater(v); } }; auto add = [&](vector v) { addlater(v); while (lateradds.size()) { auto v = lateradds.back(); lateradds.pop_back(); add_(v); } }; //v未満の個数 auto query_ = [&](vector v)->ll { ll res = 0; vector ids(bs.size()); vector gs(bs.size()); vector rgs(bs.size() + 1, 1); { int id = 0; rep(i, bs.size()) { while (bs[i][id] == 0)id++; ids[i] = id; assert(b % bs[i][id] == 0); gs[i] = b / bs[i][id]; } per(i, (int)bs.size()) { rgs[i] = rgs[i + 1] * gs[i]; } } vector adl(sz); rep(i, ids.size()) { int le = 0; if (i > 0)le = ids[i - 1] + 1; int ri = ids[i]; Rep(j, le,ri) { if (adl[j] < v[j]) { res += rgs[i]; return res; } else if (adl[j] > v[j]) { return res; } } int id = ids[i]; ll d = adl[id] / bs[i][id]; Rep(j, id, sz) { adl[j] -= d * bs[i][j]; adl[j] %= b; if (adl[j] < 0)adl[j] += b; } assert(adl[id] < bs[i][id]); if (adl[id] > v[id])return res; d = (v[id] - adl[id]) / bs[i][id]; res += rgs[i + 1] * d; if ((v[id] - adl[id]) % bs[i][id]) { res += rgs[i + 1]; return res; } Rep(j, id, sz) { adl[j] += d * bs[i][j]; adl[j] %= b; } assert(adl[id] == v[id]); rep(j, id + 1)assert(adl[j] == v[j]); } int le = 0; if (ids.size())le = ids.back(); Rep(j, le + 1, sz) { if (adl[j] < v[j]) { res += 1; return res; } else if (adl[j] > v[j]) { return res; } } return res; }; auto trans = [&](ll x) { vector res(sz); per(i, sz) { res[i] = x % b; x /= b; } return res; }; auto query = [&](ll x) { if (x == sup) { int id = 0; ll res = 1; rep(i, bs.size()) { while (bs[i][id] == 0)id++; assert(b % bs[i][id] == 0); res *= b / bs[i][id]; } return res; } ll res = query_(trans(x)); //cout <<"val "<< x << " " << res << "\n"; return res; }; //cout << "??? " << sup << "\n"; rep(i, q) { int t; ll x; cin >> t >> x; if (t == 1) { add(trans(x)); } else if (t == 2) { x--; ll le = -1, ri = sup; while (ri - le > 1) { ll mid = (le + ri) / 2; if (query(mid) > x)ri = mid; else le = mid; } if (ri == sup)le = -1; cout << le << "\n"; } else { chmin(x, sup - 1); cout << query(x+1) << "\n"; } /*cout << "hello " << i << "\n"; rep(j, bs.size())coutarray(bs[j]); cout << "fin\n";*/ /*rep(j, 10) { cout << "!? " << j<<" "<> t; rep(i, t) solve(); return 0; }