Barica and the Lily Pads

Barica is no ordinary frog. She lives in a pond that has \(N\) floating lily pads. The lily pads are numbered from \(1\) to \(N\) and each pad has a coordinate \((x_i,y_i)\). In addition, each pad \(i\) has \(f_i\) flies close to it. When Barica lands on a pad, she can eat all the flies there, earning 1 unit of energy per fly.

Barica can only jump in the following two ways from a pad located at \((x_1,y_1)\) to a pad at \((x_2,y_2)\):

• Horizontal jump: if \(x_2>x_1\) and \(y_2=y_1\), or
• Vertical jump: if \(y_2>y_1\) and \(x_2=x_1\).

Each jump costs \(K\) energy units. Barica can only perform a jump if her current energy is at least \(K\). Initially, she starts at pad 1 with 0 energy and must first eat the flies at pad 1 to gather energy. Her goal is to reach pad \(N\) while ending with as much energy as possible. Find a feasible path from pad 1 to pad \(N\) that maximizes Barica's energy. If there are multiple solutions, output any one. If it is impossible for Barica to reach pad \(N\), output -1.

inputFormat

The first line contains two integers \(N\) and \(K\) (the number of lily pads and the energy cost per jump), separated by a space.

Then \(N\) lines follow. The \(i\)-th line contains three integers \(x_i, y_i, f_i\) representing the coordinate of pad \(i\) and the number of flies near it. Pads are numbered from 1 to \(N\), and pad 1 is the starting pad while pad \(N\) is the destination.

outputFormat

If there is a valid path from pad 1 to pad \(N\), output a single line containing the sequence of pad numbers (separated by a space) that Barica follows, including pads 1 and \(N\). If there is no valid path, output -1.

sample

3 2
0 0 5
1 0 2
1 1 10

1 2 3