Марти решил отвлечь своего друга Алекса от мыслей о сочных стейках и развлечь его одной интересной задачкой.
Для начала, он случайно равновероятно выбрал n точек (x[i]
, y[i]
) (0 ≤ x[i]
, y[i]
≤ 10^9
). Затем, он случайно равновероятно выбрал два индекса i и j (1 ≤ i, j ≤ n). После чего, вычислил значение k = x[i]
* x[j]
+ y[i]
* y[j]
.
Теперь он дал Алексу n точек и число k. И просит его найти любую пару индексов a и b, такую что x[a]
* x[b]
+ y[a]
* y[b]
= k. Алексу не хочется решать эту задачу, поэтому помогите ему.
В первой строке даны два целых числа n и k (1 ≤ n ≤ 200 000, 0 ≤ k ≤ 2 * 10^18
).
В следующих n строках дано по два целых числа x[i]
и y[i]
координаты i-й точки (0 ≤ x[i]
, y[i]
≤ 10^9
). Гарантируется, что точки были сгенерированы случайно равновероятно.
Гарантируется, что k было вычислено как x[i]
* x[j]
+ y[i]
* y[j]
, где i и j были выбраны случайно равновероятно.
Выведите два целых числа a и b (1 ≤ a, b ≤ n), такие что x[a]
* x[b]
+ y[a]
* y[b]
= k. Если подходящих ответов несколько, вы можете вывести любой.