Challenge 24 Electronic Contest Practice

You are the mayor of a small planet (Procyon II). Being the economic genius that you are, your first action as mayor was selling the planet's atmosphere to an alien race of traveling merchants. For the price of the atmosphere you have bought a luxurious villa with a large pool, two sports cars and an ivory statue of yourself. There was nothing luxurious for sale for the sum that was left over after fulfilling your dreams so you went ahead and bought a tunnel digging machine.

As it turned out, your last purchase was the most useful in the end. Without atmosphere the planet is now vulnerable to meteors. You have had to move the cities underground and connected them with a system of tunnels. The tunnel digging machine has a simple and intuitive user interface - you just had to click any two cities and it would dig a tunnel between them in a straight line. Its operation however is very noisy and you are worried that this might disappoint some voters. So you have kept the total length of the tunnel network to a minimum while at the same time connecting all the cities (your sports cars would not have much of a point if you could not drive to any city).

Recently however scientists have reported that a larger meteor is now on its way towards the planet. It could very well destroy a city if it were to fall on one. It would even collapse all the tunnels leading to this city. You only have a limited number of meteor defense systems to deploy and not enough to protect all of the cities. Your task is to decide which cities it would be most economic to protect.

All cities have equal chances of being hit by the incoming meteor. Your assistant has prepared you a list of cities with the number of voters supporting you in each city. Once the giant meteor hits a city and its tunnels collapse the tunnel system might be disconnected. It will have to be restored and all this digging will lose you some more supporters. The coordinates of every city on the list were transformed to a scale in which the digging of the tunnel between two cities at unit distance would lose you 1 supporter. The list of cities to be protected would have to be the list of the cities that would lose you the highest number of supporters if they happened to be struck by the meteor.

Input:

The first line of the input file contains two numbers separated by a space character: N (the number of cities) and M (the number of meteor defense systems)

The next N lines each contain three number separated by space characters: X_i and Y_i (the coordinates of the i^th city in supporter-space) and S_i (the number of your supporters in the i^th city)

Output:

The output file consists of M lines each containing two numbers: X_i and Y_i (a city to be protected as identified by its coordinates). The order of the lines is not arbitrary.

This is the electronic variant of the problem. Read more here about submitting solutions!

Example

Input:
5 2
0 1000 1000
1000 100 0
1000 1000 0
1000 2100 0
2200 1000 0

Output:
1000 1000
0 1000