#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;
    }

  }
}