#include namespace { #pragma GCC diagnostic ignored "-Wunused-function" #include #pragma GCC diagnostic warning "-Wunused-function" using namespace std; using namespace atcoder; #define rep(i,n) for(int i = 0; i < (int)(n); i++) #define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--) #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) template bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; } template bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; } using ll = long long; using P = pair; using VI = vector; using VVI = vector; using VL = vector; using VVL = vector; tuple gcd_coeff(int x, int y) { int a = 1, b = 0, c = 0, d = 1; while (y) { int q = x / y; x = x % y; a -= c * q; b -= d * q; swap(x, y); swap(a, c); swap(b, d); } return {x, a, b, c, d}; } } int main() { ios::sync_with_stdio(false); cin.tie(0); int k, q; cin >> k >> q; VVI basis; VL right_cnt{1}; rep(_, q) { int t; ll x; cin >> t >> x; if (t == 1) { VI v; while (x) { v.emplace_back(x % k); x /= k; } auto normalize = [&](VI& v) { assert(!v.empty() && v.back()); auto [g1, x1] = internal::inv_gcd(v.back(), k); int k1 = k / g1; // x1 + i * k1, k auto [g2, x2] = internal::inv_gcd(k1, k); // int k2 = k1 / g2; int kk = k / g2; // x1 + i * k2 = 1 (mod kk) int i = ll(1 - x1) * x2 % kk; if (i < 0) i += kk; int x = (x1 + (ll)i * k1) % k; for (int& vi : v) vi = ll(vi) * x % k; assert(v.back() == g1); }; rep(i, ssize(basis)) { while (ssize(v) > ssize(basis[i])) { normalize(v); basis.insert(basis.begin() + i, v); i++; int x = k / v.back(); rep (i, ssize(v)) v[i] = (ll)v[i] * x % k; assert(v.back() == 0); while (!v.empty() && v.back() == 0) v.pop_back(); } auto& b = basis[i]; if (ssize(v) < ssize(b)) continue; assert(ssize(v) == ssize(b)); int& vv = v.back(); int& bv = b.back(); if (vv % bv) { auto [g, xa, xb, ya, yb] = gcd_coeff(vv, bv); rep(i, ssize(b)) { int pv = v[i], pb = b[i]; b[i] = ((ll)xa * pv + (ll)xb * pb) % k; v[i] = ((ll)ya * pv + (ll)yb * pb) % k; if (b[i] < 0) b[i] += k; if (v[i] < 0) v[i] += k; } assert(bv == g); } assert(vv % bv == 0); int x = vv / bv; rep(i, ssize(v)) { v[i] = v[i] - ll(x) * b[i] % k; if (v[i] < 0) v[i] += k; } assert(v.back() == 0); while (!v.empty() && v.back() == 0) v.pop_back(); } while (!v.empty()) { normalize(v); basis.emplace_back(v); int x = k / v.back(); rep (i, ssize(v)) v[i] = ((ll)v[i] * x) % k; assert(v.back() == 0); while (!v.empty() && v.back() == 0) v.pop_back(); } right_cnt.resize(ssize(basis) + 1); right_cnt.back() = 1; rrep(i, ssize(basis)) right_cnt[i] = right_cnt[i+1] * (k / basis[i].back()); } else if (t == 2) { x--; if (x >= right_cnt[0]) { cout << -1 << '\n'; continue; } int sz = ssize(basis); int ans[30]{}; rep(i, sz) { const auto& b = basis[i]; ll unit = right_cnt[i + 1]; int skip = min(x / unit, k / b.back()); x -= (ll)skip * unit; int& vv = ans[ssize(b) - 1]; int bv = b.back(); int now = vv / bv; int d = skip - now; if (d < 0) d += k; rep(i, ssize(b)) ans[i] = (ans[i] + (ll)b[i] * d) % k; } assert(x == 0); ll v = 0; rrep(i, 30) v = (k * v + ans[i]); cout << v << '\n'; } else { assert(t == 3); ll ans = 0; x++; VI v; while (x) { v.emplace_back(x % k); x /= k; } int now[30]{}; rep(i, ssize(basis)) { const auto& b = basis[i]; int cmp = 0; while (ssize(v) > ssize(b)) { int i = ssize(v) - 1; if (now[i] < v[i]) { cmp = -1; break; } else if (now[i] > v[i]) { cmp = 1; break; } v.pop_back(); } if (cmp) { if (cmp == -1) ans += right_cnt[i]; break; } int vv = ssize(v) == ssize(b) ? v.back() : 0; int bv = b.back(); int& nv = now[ssize(b) - 1]; if (nv >= bv) { int x = (k + nv % bv - nv) / bv; rep(i, ssize(b)) now[i] = (now[i] + (ll)x * b[i]) % k; assert(nv < bv); } int diff = vv - nv; if (diff < 0) break; ans += (vv - nv + bv - 1) / bv * right_cnt[i+1]; if (diff % bv) break; int x = diff / bv; rep(i, ssize(b)) now[i] = (now[i] + (ll)x * b[i]) % k; assert(nv == vv); if (i == ssize(basis) - 1) { while (!v.empty()) { int i = ssize(v) - 1; if (now[i] != v[i]) { ans += now[i] < v[i]; break; } v.pop_back(); } } } cout << ans << '\n'; } } }