Half is Good

Limits: 3 sec., 256 MiB

— Hey Zenyk, would you please help me solve a problem?

— Everything for you, my dear!

— You are given an undirected weighted graph with unique weights and at most 10 million vertices and edges. You have to find a minimum spanning forest of the graph.

— Are you kidding me?! It’s impossible under the given time and memory constraints!

— Alright, alright, calm down. Why don’t you find at least half of edges that belog to a minimum spanning forest?

— Now we’re talking!

Input

The first line of the input contains three integers \(n\), \(m\) and \(s\).

The edges of the graph must be generated in the following way:

    unsigned s; // s in the value given in the input
    unsigned getNext() {
        s = s xor (s << 13);
        s = s xor (s >> 17);
        s = s xor (s << 5);
        return s;
    }
    for (i = 0; i < m; ++i) {
        u = getNext() mod n;
        v = getNext() mod n;
        w = getNext() / 4;
        w = w * getNext(); // watch out for integer overflow
        // there is an undirected edge between u and v with weight w
    }

Please note that vertices are numbered using 0-based indices. It’s guaranteed that the weights of the edges are unique. The given graph may contain multi edges and loops.

Output

Print exactly \(\lceil \frac{m}{32} \rceil\) 32-bit unsigned integers, where the \(j\)-th bit of \(i\)-th integer is set to 1 if and only if the edge with index \(32 \times i + j\) is in your answer.

Constraints

\(1 \le n, m \le 10^7\),

\(1 \le s \le 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
4 7 47	72

Notes

Minimum spanning forest of a graph is a subset of edges with minimum total weight, such that a pair of vertices is connected if and only if it’s connected in the original graph. In other words, minimum spanning forest is the combination of minimum spanning trees of all connected components of the graph.

In the sample test case, the list of edges is the following:

1 1 179006535185096976

1 1 965163397507858962

2 2 41544785271292014

1 2 44839559531155752

2 1 2874637702340756660

1 3 2381022734547501765

3 2 1456859069025567641

The minimum spanning tree includes edges with indices 3 and 6 (0-based). Thus, answers \(8 (2^3)\), \(64 (2^6)\) and \(72 (2^3+2^6)\) are all considered correct.