Optimal Flight Route Reordering for Minimum Fuel Connectivity

A group of beings called ccj have discovered a supercluster containing n stars and m bidirectional interstellar flight routes. Each flight route requires a certain amount of fuel, denoted by \(val_i\). Two stars belong to different galaxies if and only if there is no direct flight route and no sequence of routes (i.e. a path) connecting them. Only stars can refuel spaceships, and every flight uses a simple (non‐repeating) path; furthermore, due to limitations of the fuel system, each fuel canister may only be used once. Consequently, when traveling between any two stars, the crew always chooses the most economical route that minimizes fuel consumption.

Originally, the leader ccj planned to establish a base on one star and wanted to know the minimum total fuel required at the base so that, regardless of which star is chosen, one can reach every other star in that star’s galaxy using the most economical connections. However, after a war broke out, black holes altered the spatial structure of the supercluster. The scientists now only have the fuel cost \(val_i\) for each route, and the actual endpoints of the routes are determined by a marker value \(q\) using the following formulas (all operations are performed as unsigned 32‐bit arithmetic):

\[ \begin{aligned} u_i &= \Bigl(\bigl((q^{i} \bmod 2^{32}) + i \times val_i\bigr) \bmod n + n\Bigr) \bmod n + 1,\\ v_i &= \Bigl(\bigl((q^{i} \bmod 2^{32}) - i \times val_i\bigr) \bmod n + n\Bigr) \bmod n + 1. \end{aligned} \]

If \(u_i = v_i\), then the \(i\)th flight route is discarded. In this new setting, ccj's objective has changed: for every galaxy (i.e. each connected component in the graph constructed from the flight routes) he wants to ensure that if a base is established on any star in that component, all the other stars in the same galaxy are reachable via minimum‐fuel routes. Equivalently, the fuel required in a galaxy is the sum of the fuel values of the edges in its minimum spanning tree (MST).

You are allowed to reorder the flight routes arbitrarily. Your task is to output a permutation of the flight route indices (from \(1\) to \(m\)) representing the order in which the routes are arranged. This permutation should minimize the total required fuel (the sum of the MST weights over all galaxies) across all possible galaxy structures.

Note: It can be shown that sorting the routes in non-decreasing order of \(val_i\) yields an optimal ordering. In case of ties, maintain the original order (i.e. smaller original index comes first).

inputFormat

The input is given as follows:

1. The first line contains three integers \(n\), \(m\), and \(q\): the number of stars, the number of flight routes, and the marker value, respectively.
2. The second line contains \(m\) integers: \(val_1, val_2, \ldots, val_m\), where \(val_i\) represents the fuel cost required for the \(i\)th flight route.

\(0 \leq val_i \leq 10^9\), \(1 \leq n, m \leq 10^5\), and \(0 \leq q < 2^{32}\).

outputFormat

Output a permutation of \(m\) integers (separated by spaces), representing the flight route indices in the order they are arranged. This ordering should be such that in the resulting constructed graph (after computing endpoints using the given formulas), the sum of the fuel values in the minimum spanning trees (one per connected component) is minimized. As noted, an optimal solution is obtained by sorting the indices based on \(val_i\) in non-decreasing order (with ties broken by the original index).

sample

4 3 1
3 1 2

2 3 1