eolymp
bolt
Try our new interface for solving problems
Problems

Артемида

Артемида

Зевс выделил Артемиде, богине дикой природы, прямоугольную область для выращивания леса. Левая сторона области сооответствует отрезку положительной части оси \textbf{OY}, нижняя сторона сооответствует отрезку положительной части оси \textbf{OX}, а точка \textbf{(0, 0)} -- левому нижнему углу области. Зевс потребовал, чтобы Артемида выращивала деревья только в тех точках области, которые имеют целые координаты. Артемиде нравилось, когда лес выглядит естественно, поэтому она сажала деревья таким образом, чтобы отрезок, соединяющий любую пару деревьев, не был параллелен осям \textbf{OX} и \textbf{OY}. Однажды Зевс захотел, чтобы Артемида срубила для него деревья, следуя правилам: \begin{enumerate} \item Зевс требует срубить не менее \textbf{T} деревьев. \item Чтобы получить прямоугольную футбольную площадку для будущих футбольных побед, Артемида должна срубить все деревья внутри некоторой прямоугольной области и ни одного дерева вне области. \item Стороны этой прямоугольной области должны быть параллельны осям \textbf{OX} и \textbf{OY}. \item Два противоположных угла области должны находиться в местах расположения деревьев, соответственно эти деревья также должны быть срублены. \end{enumerate} Так как Артемида любит деревья, она хочет выполнить условия, срубив при этом как можно меньше деревьев. Вы должны написать программу, которая по информации о расположении деревьев в лесу и о минимальном количестве деревьев \textbf{T}, которые необходимо срубить, выбирает область вырубки деревьев для Артемиды. \InputFile Во входном файле первая строка содержит одно целое число \textbf{N} -- количество деревьев в лесу. Вторая строка содержит одно целое число \textbf{T} -- минимальное количество деревьев для вырубки. Последующие \textbf{N} строк описывают положения \textbf{N} деревьев. Каждая из этих строк содержит два целых числа: \textbf{X} и \textbf{Y}, \textbf{x}-координату и затем \textbf{y}-координату дерева. Для всех тестов \textbf{1} < \textbf{N} ≤ \textbf{20000}, \textbf{0} ≤ \textbf{X}, \textbf{Y} ≤ \textbf{64000} и \textbf{1} < \textbf{T} ≤ \textbf{N}. В \textbf{50}\% тестов: \textbf{1} < \textbf{N} < \textbf{5000}. \OutputFile Выходной файл должен содержать одну строку с двумя целыми числами \textbf{I} и \textbf{J}, разделенными одним пробелом. Артемида должна рассматривать \textbf{I}--ое дерево с координатами, заданными в строке \textbf{I+2} входного файла, и \textbf{J}--ое дерево с координатами, заданными в строке \textbf{J+2} входного файла, как углы области для вырубки деревьев. Порядок вывода этих двух чисел не существенен. Если существует несколько вариантов выбора такой пары деревьев, вы должны найти и выдать только один из них. Для всех тестов существует хотя бы одно решение.
Time limit 1 second
Memory limit 64 MiB
Input example #1
500
30
1272 1
4 5
5 7
1265 9
1264 10
14 11
17 12
1257 15
1254 18
23 19
24 22
1244 24
1243 27
35 29
39 30
1236 32
1233 34
43 37
46 40
1225 41
1224 44
54 45
58 46
1219 47
1218 49
66 52
70 53
1209 56
1207 60
82 63
86 67
1199 68
1195 69
91 72
94 74
1188 75
1187 78
100 82
103 86
1179 87
1178 88
112 89
114 92
1170 93
1169 95
122 96
123 99
1160 100
1156 104
132 106
134 107
1148 109
1145 113
141 114
144 118
1137 122
1133 126
150 128
153 130
1125 134
1121 138
159 141
162 143
1115 145
1111 146
169 148
170 149
1102 152
1101 155
180 158
183 161
1095 164
1094 165
192 166
194 167
1087 171
1085 175
204 177
205 181
1075 183
1073 185
215 189
217 191
1066 193
1062 197
227 199
229 200
1055 204
1053 207
238 209
241 213
1047 216
1044 218
249 222
250 225
1036 229
1033 232
258 233
262 237
1027 241
1026 242
268 246
269 247
1020 248
1019 251
278 253
280 255
1008 256
1004 259
291 262
292 266
996 270
992 274
297 276
300 278
987 279
983 280
305 283
306 287
974 291
972 292
313 296
316 300
963 301
961 304
326 307
3
...
Output example #1
Empty file.
  Yours Sincerely, CAP
Source IOI-2004