#P15488. [IOI 2004] Artemis

[IOI 2004] Artemis

说明

宙斯给了旷野女神阿尔忒弥斯一块长方形的地来种一片森林。

将这块地的左侧作为 yy 轴正半轴,底部作为 xx 轴正半轴,以及这块地的左下角作为 (0,0)(0,0)

宙斯让阿尔忒弥斯只在这块地的整数坐标点上种树。阿尔忒弥斯喜欢让森林看起来很自然,因此种植树木的方式是,保证两棵树的连线永远不会平行于 xx 轴或 yy 轴。

有时,宙斯希望阿尔忒弥斯为他砍树。树木将按如下方式砍伐:

  1. 给定 TT,宙斯希望至少为他砍伐 TT 棵树,
  2. 为了获得一个矩形球场,阿尔忒弥斯要砍伐一个矩形区域内的所有树木,而不砍这个矩形区域外的树木,
  3. 该矩形区域的边应平行于 xx 轴和 yy 轴,
  4. 该区域的两个相对角落必须位于树木上,因此这些角落的树木也会被砍伐。

由于阿尔忒弥斯喜欢这些树,她希望在尽可能少砍伐树木的同时满足这些条件。您需要编写一个程序,根据森林信息和要砍伐的最小树木数量 TT,为阿尔忒弥斯选择一个砍伐树木的区域。

输入格式

第一行一个整数 NN:森林里的树的数量。

第二行一个整数 TT:被砍伐的树的最小数量。

接下来 NN 行描述了 NN 棵树的位置。每行两个整数 XXYY:树的 XX 坐标和 YY 坐标。

输出格式

一行两个整数 IIJJ,用一个空格分隔:阿尔忒弥斯应使用第 II 棵树(位于输入文件的 I+2I+2 行)和第 JJ 棵树(位于输入文件的 J+2J+2 行)作为砍伐树木的区域的角。这两个数字的顺序不重要。

可能有多种方法选择这些树,您需要找到并输出其中一种。对于所有测试用例,至少存在一个解决方案。

3
2
1 1
2 3
5 6 
1 2

提示

在所有测试点中,1<N200001<N\le 200000X,Y640000\le X,Y\le 640001<TN1<T\le N

此外,在 50%50\% 的测试点中,1<N<50001<N<5000