На данный момент Тайни изучает вычислительную геометрию. Когда он пытался решить задачу под названием «Ближайшая пара точек на плоскости», то обнаружил, что код, имеющий неверную временную сложность, был засчитан как правильный, а не отвергнут по причине превышения лимита времени.

Задача выглядит следующим образом. Вам дано n точек на плоскости, найдите пару точек, между которыми минимальное расстояние. Расстояние между (x₁, y₁) и (x₂, y₂) равняется .

Псевдокод кода с неверной сложностью имеет следующий вид:

ввести n
for i from 1 to n
    ввести координаты i-той точки в переменную p[i]
отсортировать массив p[] в первую очередь по возрастанию x координаты, во вторую по возрастанию y
d=INF        //здесь INF — это достаточно большое число
tot=0
for i from 1 to n
    for j from (i+1) to n
        ++tot
        if (p[j].x-p[i].x>=d) then break    //обратите внимание, что "break" используется                         
                                            //только для того, чтобы выйти из цикла "for j"
        d=min(d,distance(p[i],p[j]))
вывести d

В этом коде значение tot можно рассматривать как время выполнения кода. Так как компьютер выполняет фиксированное количество операций в секунду, значение tot не должно превышать k для того, чтобы не превысить лимит времени.

Вы — первоклассный хакер. Не поможете Тайни сгенерировать данные для теста, на которых код получит превышение лимита времени?