#include <iostream>
#include <vector>
#include <string>
#include <iomanip>
#include <queue>
#include <cmath>
#include <algorithm>
#include <unordered_map>
#include <tuple>
#include <iomanip>
#include <stdio.h>
#include <map>
#include <bitset>
#include <set>
#include <stack>
#include <queue>
#include <unordered_set>
#include <cassert>
#include <stdlib.h>
#include <time.h>
#include <random>


//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,sse3,sse4");
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("fast-math")
//#pragma GCC target("avx2")
//#pragma GCC optimize("section-anchors")
//#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
//#pragma GCC optimize("vpt")
//#pragma GCC optimize("rename-registers")
//#pragma GCC optimize("move-loop-invariants")
//#pragma GCC optimize("unswitch-loops")
//#pragma GCC optimize("function-sections")
//#pragma GCC optimize("data-sections")

//#define int long long
#define ll long long
#define ull unsigned long long
#define all(a) (a).begin(), (a).end()
#define pii pair<int, int>
#define pb push_back
#define ld long double


using namespace std;

//const int INF = 1e17;
//const int mod = 2600000069;
//const int p = 179;

vector<int> p, h, m, r;
const ll mod = 1e6 + 3;
ll zerg = 0, n, q;

int par(int v) {
    if (p[v] == v) return v;
    return p[v] = par(p[v]);
}

void join(int u, int v) {
    u = par(u);
    v = par(v);
    if (u != v) {
        if (h[u] > h[v]) swap(u, v);
        for (int i = 0; i < n; i++) {
            if (par(i) == u) r[i] += m[v];
            else if (par(i) == v) r[i] += m[u];
        }
        p[u] = v;
        m[v] += m[u];
        if (h[u] == h[v]) h[v]++;
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    p.resize(n);
    for (int i = 0; i < n; i++) p[i] = i;
    h.assign(n, 0);
    m.assign(n, 0);
    r.assign(n, 0);
    int t, u, v;
    while (q--) {
        cin >> t;
        if (t == 1) {
            cin >> u;
            u = (u + zerg) % n;
            m[par(u)]++;
            zerg = (30 * zerg + 239) % mod;
        } else if (t == 2) {
            cin >> u >> v;
            u = (u + zerg) % n;
            v = (v + zerg) % n;
            if (par(u) != par(v)) {
                join(u, v);
                zerg = (13 * zerg + 11) % mod;
            }
        } else {
            cin >> u;
            u = (u + zerg) % n;
            int w = m[par(u)] - r[u];
            r[u] += w;
            cout << w << "\n";
            zerg = (100500LL * zerg + w) % mod;
        }
    }
}
/*
4 10
1 0
1 2
1 1
1 2
3 1
2 1 2
1 3
3 3
2 3 2
3 2
*/