#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>
#ifdef CKISEKI
#define safe cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(a...) debug_(#a, a)
#define orange(a...) orange_(#a, a)
using std::cerr;
template <typename ...T>
void debug_(const char *s, T ...a) {
    cerr << "\e[1;32m(" << s << ") = (";
    int cnt = sizeof...(T);
    (..., (cerr << a << (--cnt ? ", " : ")\e[0m\n")));
}
template <typename I>
void orange_(const char *s, I L, I R) {
    cerr << "\e[1;32m[ " << s << " ] = [ ";
    for (int f = 0; L != R; ++L)
        cerr << (f++ ? ", " : "") << *L;
    cerr << " ]\e[0m\n";
}
#else
#define safe ((void)0)
#define debug(...) ((void)0)
#define orange(...) ((void)0)
#endif

#define all(v) begin(v),end(v)

using namespace std;

// #define int int_fast32_t
// #define unsigned uint_fast32_t

namespace {
const int maxn = 10000025;
const int SHIFT = 22;
const int maxc = 1 << SHIFT;
const int mask = (1 << SHIFT) - 1;

int pa[maxn];
int label[maxn];

int rk[maxn];
int perm[maxn];

unsigned ans[maxn >> 5];

int cnt[maxc];

inline unsigned getNext(unsigned &s) {
    s = s ^ (s << 13);
    s = s ^ (s >> 17);
    s = s ^ (s << 5);
    return s;
}

int anc(int x) {
    return pa[x]<0 ? x : pa[x]=anc(pa[x]);
}
bool join(int x, int y) {
    x = anc(x);
    y = anc(y);
    if (x == y) return false;
    if (pa[x] > pa[y])
        swap(x, y);
    debug(pa[x], pa[y]);
    int nrk = (pa[x]==pa[y] ? pa[x]-1 : pa[x]);
    pa[y] = x;
    pa[x] = nrk;
    return true;
}

struct Barret {
    using big = __uint128_t;
    big R;
    int m;
    Barret(int t_m) : R((big(1) << 64) / t_m), m(t_m) {}
    int reduce(unsigned a) {
        unsigned q = (a * R) >> 64;
        unsigned r = a - m * q;
        return r >= m ? r - m : r;
    }
};

}

signed main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    int n, m;
    unsigned init_s;
    cin >> n >> m >> init_s;
    
    int shift = 0;
    
    for (int i = 0; i < m; i++)
        rk[i] = i;
    for (int i = 0; i < m; i++)
        perm[i] = i;

    for (int i = 0; i < m; i++) {
        int u = getNext(s);
        int v = getNext(s);
        long long w = getNext(s) / 4;
        w *= getNext(s);
        edge_u[i] = u;
        edge_v[i] = v;
        edge_w[i] = w;
    }

    for (int t = 0; t < 3; t++) {
        unsigned s = init_s;

        orange(perm, perm + m);
        orange(label, label + m);

        memset(cnt, 0, sizeof(cnt));
        // for (int i = 0; i < maxc; i++)
        //     cnt[i] = 0;
        for (int i = 0; i < m; i++)
            ++cnt[label[i]];
        for (int i = 1; i < maxc; i++)
            cnt[i] += cnt[i - 1];

        for (int i = m - 1; i >= 0; i--) {
            rk[perm[i]] = --cnt[label[perm[i]]];
        }
        for (int i = 0; i < m; i++)
            perm[rk[i]] = i;

        orange(rk, rk + m);
        orange(perm, perm + m);

        shift += SHIFT;
    }

    // DSU init
    for (int i = 0; i < n; i++)
        pa[i] = -1;

// #define edge_u rk
// #define edge_v label
    int *edge_u = rk;
    int *edge_v = label;
    // vector<long long> edge_w(m);

    Barret b(n);
    unsigned s = init_s;
    for (int i = 0; i < m; i++) {
        int u = b.reduce(getNext(s));
        int v = b.reduce(getNext(s));
        getNext(s);
        getNext(s);
        // long long w = getNext(s) / 4;
        // w *= getNext(s);
        edge_u[i] = u;
        edge_v[i] = v;
        // edge_w[i] = w;
        // debug(u, v, w);
    }

    int cnt = 0;
    for (int i = 0; i < m; i++) {
        int p = perm[i];
        // debug(edge_u[p], edge_v[p], edge_w[p]);
        if (join(edge_u[p], edge_v[p])) {
            ans[p >> 5] |= 1u << (p % 32);
            if (++cnt >= (n - 1) / 2) {
                break;
            }
        }
    }

    const int L = (m + 31) / 32;
    for (int i = 0; i < L; i++) {
        debug(bitset<32>(ans[i]));
        cout << ans[i] << (i+1==L ? '\n' : ' ');
    }

    return 0;
}

answer.code: In function ‘int main()’:
answer.code:102:25: error: ‘s’ was not declared in this scope
  102 |         int u = getNext(s);
      |                         ^
answer.code:106:9: error: ‘edge_u’ was not declared in this scope
  106 |         edge_u[i] = u;
      |         ^~~~~~
answer.code:107:9: error: ‘edge_v’ was not declared in this scope
  107 |         edge_v[i] = v;
      |         ^~~~~~
answer.code:108:9: error: ‘edge_w’ was not declared in this scope
  108 |         edge_w[i] = w;
      |         ^~~~~~