Будем считать, что карта Адриатического моря представляет собой сетку, состоящую из единичных квадратиков, организованных в \(2500\) рядов и \(2500\) столбцов. Ряды пронумерованы от \(1\) до \(2500\) с севера на юг, столбцы пронумерованы от \(1\) до \(2500\) с запада на восток. В море есть N островов, пронумерованных от 1 до N и каждый остров находится внутри некоторого единичного квадрата сетки. Позиция острова K задана его координатами — рядом \(R_k\) и столбцом \(C_k\). Никакие два острова не находятся в одном квадрате.

Из за ветра и морских течений, за один шаг переплыть с одного острова на другой можно только, если они расположены в северо-западном или юго-восточном направлении друг относительно друга.

Точнее, можно переплыть с острова \(A\) на остров \(B\) за один шах, если или \(R_A \lt R_B\) и \(C_A \lt C_B\), или \(R_A \gt R_B\) и \(C_A \gt C_B\). При этом расстояние между островами или наличие островов по дороге не влияет на возможность доплыть с одного острова на другой. Если нельзя доплыть с одного острова на другой напрямую, иногда можно доплыть с использованием промежуточных островов более чем за один шаг. Определим как расстояние между островами величину, равную числу шагов, необходимых, чтобы переплыть с одного острова на другой.

Рассмотрим остров K. Для каждого острова определим, какое минимальное число шагов можно переплыть с него на K. Просуммируем эти числа и получим некоторую величину, характеризующую удаленность K от остальных островов. Требуется найти это число для всех островов. Гарантируется, что в тестах острова расположены так, что с каждого острова можно попасть на каждый.