#include #include #include #include #include using namespace std; using ll = long long; using vi = vector; using v2i = vector; using pii = pair; constexpr ll X = 1.1e18; pii exgcd(int a, int b) { if (b == 0) { return {1, 0}; } auto [k1, k2] = exgcd(b, a % b); return {k2, k1 - a / b * k2}; } ll solve(const v2i &base, int k, ll x) { x--; int n = base.size(); int xd[n]; for (int i = 0; i < n; i++) { if (!base[i].empty()) { xd[i] = x % (k / base[i][i]); x /= k / base[i][i]; } } if (x > 0) { return -1; } int ans[n]; fill(ans, ans + n, 0); for (int i = n - 1; i >= 0; i--) { if (!base[i].empty()) { int t = ((xd[i] - ans[i] / base[i][i]) % k + k) % k; for (int j = 0; j < n; j++) { ans[j] = (ans[j] + 1ll * t * base[i][j]) % k; } } } ll t = 0; for (int i = n - 1; i >= 0; i--) { t = t * k + ans[i]; } return t; } int main() { int k, q; cin >> k >> q; int n = log(X) / log(k) + 1; v2i base(n); while (q--) { int op; ll x; cin >> op >> x; if (op == 1) { int xd[n]; for (int i = 0; i < n; i++) { xd[i] = x % k; x /= k; } for (int i = n - 1; i >= 0; i--) { if (xd[i] == 0) { continue; } auto [k1, k2] = exgcd(xd[i], base[i].empty() ? k : base[i][i]); if (base[i].empty()) { base[i] = vi(n); } if (k2 == 0) { for (int j = 0; j < n; j++) { swap(base[i][j], xd[j]); } swap(k1, k2); } for (int j = 0; j < n; j++) { base[i][j] = ((1ll * k1 * xd[j] + 1ll * k2 * base[i][j]) % k + k) % k; } for (int j = 0; j < n; j++) { xd[j] = ((xd[j] - 1ll * (xd[i] / base[i][i]) * base[i][j]) % k + k) % k; } } } else if (op == 2) { cout << solve(base, k, x) << endl; } else { ll l = 0, r = x + 2; while (r - l > 1) { ll mid = (l + r) / 2; ll t = solve(base, k, mid); if (t <= x && t != -1) { l = mid; } else { r = mid; } } cout << l << endl; } } return 0; }