Есть $$$n$$$ точек на плоскости. Многоугольник, сформированный этими $$$n$$$ точками, строго выпуклый, то есть многоугольник выпуклый и нет трех коллинеарных точек (то есть лежащих на одной прямой). Точки пронумерованы от $$$1$$$ до $$$n$$$ по часовой стрелке.

Определим расстояние между двумя точками $$$p_1 = (x_1, y_1)$$$ и $$$p_2 = (x_2, y_2)$$$ как их манхэттенское расстояние: $$$$$$d(p_1, p_2) = |x_1 - x_2| + |y_1 - y_2|.$$$$$$

Более того, определим периметр многоугольника как сумму манхэттенских расстояний между всеми соседними парами точек на нем; если точки на многоугольнике упорядочены как $$$p_1, p_2, \ldots, p_k$$$ $$$(k \geq 3)$$$, тогда периметр многоугольника равен $$$d(p_1, p_2) + d(p_2, p_3) + \ldots + d(p_k, p_1)$$$.

Для некоторого параметра $$$k$$$ рассмотрим все многоугольники, которые могут быть сформированы из любых $$$k$$$ точек заданного многоугольникв и не самопересекаются. Для каждого такого многоугольника рассмотрим его периметр. Определим $$$f(k)$$$ как максимальный периметр среди всех таких многоугольников.

Обратите внимание, что при проверке многоугольника на самопересечение, ребра многоугольника рисуются как прямые линии. Например, на следующих рисунках:

В многоугольнике, который изображен посередине, последовательность точек ($$$p_1, p_3, p_2, p_4$$$) неправильная потому, что многоугольник самопересекается. Правый многоугольник (ребра которого напоминают Манхэттенское расстояние) имеет такую же последовательность и не самопересекается, но мы рассматриваем ребра как прямые отрезки. Правильный способ нарисовать этот многоугольник — это использовать последовательность ($$$p_1, p_2, p_3, p_4$$$), пример которого можно увидеть на левом рисунке.

Вычислите $$$f(3), f(4), \ldots, f(n)$$$. Другими словами, найдите максимально возможный периметр для каждого количества точек (то есть от $$$3$$$ до $$$n$$$).