— 嘿 Zenyk，你能帮我解决一个问题吗？ — 没问题，亲爱的！ — 你现在有一个无向加权图，权重唯一，且最多有 1000 万个顶点和边。你需要找到该图的一个最小生成森林。 — 你在开玩笑吗？！在给定的时间和内存限制下这根本不可能！ — 好吧，冷静点。你为什么不试着找出至少一半属于最小生成森林的边呢？ — 这还差不多！

输入格式

输入的第一行包含三个整数 $n, m$ 和 $s$ ($1 \le n, m \le 10^7, 1 \le s \le 10^9$)。

图的边必须通过以下方式生成：

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
}

请注意，顶点使用 0-based 索引。保证边的权重是唯一的。给定的图可能包含重边和自环。

输出格式

输出恰好 $\lceil \frac{m}{32} \rceil$ 个 32 位无符号整数，其中第 $i$ 个整数的第 $j$ 位被设为 1，当且仅当索引为 $32 \times i + j$ 的边在你的答案中。

样例

输入 1

4 7 47

输出 1

72

说明

图的最小生成森林是权重之和最小的边子集，使得一对顶点连通当且仅当它们在原图中连通。换句话说，最小生成森林是图中所有连通分量的最小生成树的组合。

在样例测试中，边的列表如下：

1 1 179006535185096976
1 1 965163397507858962
2 2 41544785271292014
1 2 44839559531155752
2 1 2874637702340756660
1 3 2381022734547501765
3 2 1456859069025567641

最小生成树包含索引为 3 和 6（0-based）的边。因此，答案 $8(2^3)$、$64(2^6)$ 和 $72(2^3 + 2^6)$ 均被视为正确。