#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5, mod = 998244353;
set<set<int>> edges;
int par[N];
vector<int> adj[N];
struct DSU {
vector<int> par, sz;
DSU() {
sz.assign(N, 1);
par.resize(N);
iota(par.begin(), par.end(), 0);
}
int F(int x) { return par[x] == x ? x : (par[x] = F(par[x])); }
void mrg(int u, int v) {
u = F(u), v = F(v);
sz[v] += sz[u];
par[u] = v;
}
bool check(int u, int v) {
int f = sz[F(u)], s = sz[F(v)];
return f > s;
}
} dsu;
void mrg(int u, int v) {
if (!par[u]) {
par[u] = v;
} else if (!par[v]) {
par[v] = u;
} else {
if (dsu.check(u, v)) swap(u, v);
queue<pair<int, int>> q;
q.push({u, u});
par[u] = v;
while (q.size()) {
auto [nd, p] = q.front();
q.pop();
for (int &x: adj[nd]) {
if (x == p)continue;
par[x] = nd;
q.push({x, nd});
}
}
}
dsu.mrg(u, v);
adj[u].emplace_back(v);
adj[v].emplace_back(u);
edges.insert({u, v});
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
iota(par, par + N, 0);
int n, q;
cin >> n >> q;
int l = 1;
for (int i = 0; i < q; ++i) {
int a, b, c;
cin >> a >> b >> c;
int t = 1 + (a * l % mod % 2);
int u = 1 + (b * l % mod % n);
int v = 1 + (c * l % mod % n);
if (t == 1) {
mrg(u, v);
} else {
int pu = par[u], pv = par[v];
int ans = 0;
if (pu == pv && pv) {
ans = pu;
} else if (pu && edges.count({pu, v})) {
ans = pu;
} else if (pv && edges.count({pv, u})) {
ans = pv;
}
cout << ans << '\n';
l = ans + 1;
}
}
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwojZGVmaW5lIGludCBsb25nIGxvbmcKY29uc3QgaW50IE4gPSAxZTUgKyA1LCBtb2QgPSA5OTgyNDQzNTM7CnNldDxzZXQ8aW50Pj4gZWRnZXM7CmludCBwYXJbTl07CnZlY3RvcjxpbnQ+IGFkaltOXTsKCnN0cnVjdCBEU1UgewogIHZlY3RvcjxpbnQ+IHBhciwgc3o7CgogIERTVSgpIHsKICAgIHN6LmFzc2lnbihOLCAxKTsKICAgIHBhci5yZXNpemUoTik7CiAgICBpb3RhKHBhci5iZWdpbigpLCBwYXIuZW5kKCksIDApOwogIH0KCiAgaW50IEYoaW50IHgpIHsgcmV0dXJuIHBhclt4XSA9PSB4ID8geCA6IChwYXJbeF0gPSBGKHBhclt4XSkpOyB9CgogIHZvaWQgbXJnKGludCB1LCBpbnQgdikgewogICAgdSA9IEYodSksIHYgPSBGKHYpOwogICAgc3pbdl0gKz0gc3pbdV07CiAgICBwYXJbdV0gPSB2OwogIH0KCiAgYm9vbCBjaGVjayhpbnQgdSwgaW50IHYpIHsKICAgIGludCBmID0gc3pbRih1KV0sIHMgPSBzeltGKHYpXTsKICAgIHJldHVybiBmID4gczsKICB9Cn0gZHN1OwoKdm9pZCBtcmcoaW50IHUsIGludCB2KSB7CiAgaWYgKCFwYXJbdV0pIHsKICAgIHBhclt1XSA9IHY7CiAgfSBlbHNlIGlmICghcGFyW3ZdKSB7CiAgICBwYXJbdl0gPSB1OwogIH0gZWxzZSB7CiAgICBpZiAoZHN1LmNoZWNrKHUsIHYpKSBzd2FwKHUsIHYpOwogICAgcXVldWU8cGFpcjxpbnQsIGludD4+IHE7CiAgICBxLnB1c2goe3UsIHV9KTsKICAgIHBhclt1XSA9IHY7CiAgICB3aGlsZSAocS5zaXplKCkpIHsKICAgICAgYXV0byBbbmQsIHBdID0gcS5mcm9udCgpOwogICAgICBxLnBvcCgpOwogICAgICBmb3IgKGludCAmeDogYWRqW25kXSkgewogICAgICAgIGlmICh4ID09IHApY29udGludWU7CiAgICAgICAgcGFyW3hdID0gbmQ7CiAgICAgICAgcS5wdXNoKHt4LCBuZH0pOwogICAgICB9CiAgICB9CiAgfQogIGRzdS5tcmcodSwgdik7CiAgYWRqW3VdLmVtcGxhY2VfYmFjayh2KTsKICBhZGpbdl0uZW1wbGFjZV9iYWNrKHUpOwogIGVkZ2VzLmluc2VydCh7dSwgdn0pOwp9CgppbnQzMl90IG1haW4oKSB7CiAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgY2luLnRpZShudWxscHRyKTsKICBpb3RhKHBhciwgcGFyICsgTiwgMCk7CiAgaW50IG4sIHE7CiAgY2luID4+IG4gPj4gcTsKICBpbnQgbCA9IDE7CiAgZm9yIChpbnQgaSA9IDA7IGkgPCBxOyArK2kpIHsKICAgIGludCBhLCBiLCBjOwogICAgY2luID4+IGEgPj4gYiA+PiBjOwogICAgaW50IHQgPSAxICsgKGEgKiBsICUgbW9kICUgMik7CiAgICBpbnQgdSA9IDEgKyAoYiAqIGwgJSBtb2QgJSBuKTsKICAgIGludCB2ID0gMSArIChjICogbCAlIG1vZCAlIG4pOwogICAgaWYgKHQgPT0gMSkgewogICAgICBtcmcodSwgdik7CiAgICB9IGVsc2UgewogICAgICBpbnQgcHUgPSBwYXJbdV0sIHB2ID0gcGFyW3ZdOwogICAgICBpbnQgYW5zID0gMDsKICAgICAgaWYgKHB1ID09IHB2ICYmIHB2KSB7CiAgICAgICAgYW5zID0gcHU7CiAgICAgIH0gZWxzZSBpZiAocHUgJiYgZWRnZXMuY291bnQoe3B1LCB2fSkpIHsKICAgICAgICBhbnMgPSBwdTsKICAgICAgfSBlbHNlIGlmIChwdiAmJiBlZGdlcy5jb3VudCh7cHYsIHV9KSkgewogICAgICAgIGFucyA9IHB2OwogICAgICB9CiAgICAgIGNvdXQgPDwgYW5zIDw8ICdcbic7CiAgICAgIGwgPSBhbnMgKyAxOwogICAgfQoKICB9Cn0=