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} входного файла, как углы области для вырубки деревьев. Порядок вывода этих двух чисел не существенен. Если существует несколько вариантов выбора такой пары деревьев, вы должны найти и выдать только один из них. Для всех тестов существует хотя бы одно решение.
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