Minimal Spanning Tree

Given a connected, undirected, weight graph G, your task is to select a subset of edges so that after deleting all the other edges, the graph G is still connected. If there are multiple ways to do this, you should choose the way that minimize the sum of the weight of these selected edges.

Please note that the graph G might be very large. we'll give you two numbers: N, and seed, N is number of nodes in graph G, the following psuedo-code shows how to to generate graph G.



Here ⊕ represents bitwise xor (exclusive-or).

Input contains several test cases, please process till EOF.
For each test case, the only line contains two numbers: N and seed.(1 ≤ N ≤ 10000000, 1 ≤ seed ≤ 2333332)

For each test case output one number, the minimal sum of weight of the edges you selected.

6 2877
2 17886
3 22452

2157810
259637
1352144

Fudan University

2014 Multi-University Training Contest 3