Artemis
Zeus has granted Artemis, the goddess of the wild, a rectangular plot for cultivating a forest. The left boundary of this plot aligns with a segment of the positive OY axis, while the bottom boundary aligns with a segment of the positive OX axis. The point (0, 0) marks the lower left corner of the plot. Zeus instructed Artemis to plant trees only at points with integer coordinates. To maintain a natural appearance, Artemis ensured that the line segment connecting any two trees was not parallel to either the OX or OY axes.
One day, Zeus requested Artemis to cut down some trees, adhering to the following rules:
At least T trees must be cut down.
To create a rectangular football field for future victories, Artemis must remove all trees within a specified rectangular area and none outside it.
The sides of this rectangular area must be parallel to the OX and OY axes.
Two opposite corners of the area must be located at the positions of trees, and these trees must also be cut down.
Artemis, who cherishes her trees, wants to meet these requirements by cutting down the fewest number of trees possible. Your task is to write a program that, given the layout of the trees and the minimum number of trees T that need to be cut, determines the optimal area for Artemis to clear.
Input
The first line of the input file contains a single integer N – the total number of trees in the forest. The second line contains a single integer T – the minimum number of trees to be cut down. The following N lines each describe the position of a tree with two integers: X and Y, representing the x-coordinate and y-coordinate, respectively.
For all test cases, 1 < N ≤ 20000, 0 ≤ X, Y ≤ 64000, and 1 < T ≤ N. In 50% of the test cases: 1 < N < 5000.
Output
The output should consist of one line with two integers I and J, separated by a single space. These integers represent the indices of the trees that Artemis should consider as the corners of the tree-cutting area. The coordinates of the I-th tree are given on line I+2 of the input file, and the coordinates of the J-th tree are on line J+2. The order of these numbers in the output does not matter. If multiple solutions exist, you need to provide only one. There is guaranteed to be at least one solution for all test cases.