Найближчі точки

Обмеження: 2 сек., 256 МіБ

На площині знаходиться \(n\) точок пронумерованих від \(1\) до \(n\) з координатами \((x_i, y_i)\).

Відстань між точками з індексами \(i\) та \(j\) визначається як \(dist(i, j) = min(|x_i-x_j|, |y_i-y_j|)\).

Знайдіть пару точок з найменшою можливою відстанню.

Вхідні дані

У першому рядку \(n\) — кількість точок на площині. В наступних \(n\) рядках дано по 2 цілі числа \(x_i\) та \(y_i\) — координати \(i\)-ої точки.

Вихідні дані

В одному рядку виведіть через пропуск два цілі числа \(i\) та \(j\) — індекси точок між якими найменша відстань.

Якщо таких пар точок більш ніж одна, то знайдіть пару для якої мінімізується \(i + j\).

Якщо і таких пар декілька, то серед них знайдіть пару з мінімальним \(i\).

Обмеження

\(2 \le n \le 100000\),

\(-10^9 \le x_i, y_i \le 10^9\).

Приклади