Optimal Ruin Visiting Order

You are given a grid with dimensions \(m \times n\). Scattered in this grid are several ruins; each ruin is located at a specific coordinate and has an associated treasure weight. Starting at a given coordinate, you must decide an order to visit all ruins so that the total travel time is minimized.

The travel time between two points is calculated using the Manhattan distance. In particular, when traveling from point \(P\) to point \(Q\), the travel time is determined by the formula:

$$ T = d(P, Q) \times \Bigl(1 + W\Bigr) $$

where the Manhattan distance is defined as:

$$ d(P, Q) = |x_1 - x_2| + |y_1 - y_2|, $$

and \(W\) is the total weight you have already collected from ruins visited before reaching \(Q\).

Your task is to output the visiting order of the ruins (each ruin represented by its coordinates) in a single line such that every ruin is visited exactly once and the overall travel time is minimized.

inputFormat

The input is read from standard input (stdin) and is formatted as follows:

• The first line contains two integers \(m\) and \(n\) denoting the dimensions of the grid.
• The next several lines each contain three integers: the x-coordinate, the y-coordinate, and the treasure weight of a ruin. There will be at least one ruin.
• The last line contains two integers that represent the starting coordinate.

outputFormat

Output a single line to standard output (stdout) that contains the optimal visiting order of ruins. The order should be represented as a sequence of numbers, where every two consecutive numbers represent the x and y coordinates of a ruin in the order they are visited.

## sample

5 5
2 3 10
4 4 20
1 1 5
3 2 15
4 1 25
3 3

1 1 2 3 3 2 4 4 4 1