Половина --- це добре

Обмеження: 3 сек., 256 МіБ

— Гей, Зенику, будь ласка, допоможи мені розв’язати задачу.

— Усе для тебе, моя дорога!

— Тобі дано неорієнтований зважений граф з унікальними вагами та не більше ніж 10 мільйонами вершин і ребер. Тобі треба знайти мінімальний кістяковий ліс графу.

— Жартуєш?! Це неможливо за таких обмежень часу і пам’яті!

— Гаразд, гаразд, заспокойся. Чому б тобі не знайти хоча б половину ребер мінімального кістякового лісу?

— Інша справа!

Вхідні дані

Перший рядок містить три цілі числа \(n\), \(m\) і \(s\).

Ребра графу згенеровані таким чином:

    unsigned s; // s - задане значення
    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(); // стережіться цілочисельного переповнення
        // є неорієнтоване ребро між u та v з вагою w
    }

Будь ласка, зверніть увагу, що вершини нумеруються з нуля

Гарантується, що ваги ребер унікальні.

Граф може містити мультиребра та петлі.

Вихідні дані

Виведіть рівно \(\lceil \frac{m}{32} \rceil\) 32-бітових беззнакових цілих чисел, де \(j\)-ий біт \(i\)-го числа встановлений в 1 тоді й тільки тоді, коли ребро з індексом \(32 i + j\) є в вашій відповіді.

Обмеження

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

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

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 7 47	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-індексація). Тому всі з відповідей \(8 (2^3)\), \(64 (2^6)\) та \(72 (2^3+2^6)\) вважаються правильними.