Artemis#2124
Zeus, the god of the skies, granted Artemis (the goddess of the wild) a rectangular area to cultivate a forest. The left side of the plot lies along the positive segment of the axis, the bottom along the positive segment of the axis, and the point marks the lower left corner of the area. Zeus instructed Artemis to plant trees only at points with integer coordinates. To keep the forest natural, Artemis arranged the trees so that the segment joining any two trees is never parallel to the or axes.
One day, Zeus asked Artemis to cut down some trees, following these rules:
At least trees must be cut down.
To create a rectangular football field, Artemis must cut down all trees located inside a specific rectangular area and none outside it.
The sides of this rectangular area must be parallel to the and axes.
Two opposite corners of the area must coincide with trees' positions, and those trees must also be cut down.
As she loves her trees, Artemis wants to meet this requirement while cutting down as few trees as possible. Your task is to write a program which, given the trees' positions and the minimum number of trees to be cut, chooses the area for cutting.
The first line contains a single integer — the number of trees. The second line contains an integer — the minimum number of trees to be cut. The next lines describe the positions of the trees. Each line contains two integers: and , the -coordinate and the -coordinate of a tree.
For all cases: 1 < N \leq 20000, 0 \leq X, Y \leq 64000, 1 < T \leq N. In of the cases: 1 < N < 5000.
The output should consist of a single line with two integers and separated by a space. Artemis must consider the tree in the (I+2)-nd line and the tree in the (J+2)-nd line of the input file as the corners of the tree-removal rectangle. The order of and in the output does not matter. If there are multiple valid pairs, output any one. There is guaranteed to be at least one solution for all test cases.
Example 1