Будем считать, что карта Адриатического моря представляет собой сетку, состоящую из единичных квадратиков, организованных в \(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 от остальных островов. Требуется найти это число для всех островов. Гарантируется, что в тестах острова расположены так, что с каждого острова можно попасть на каждый.

Байтазар, король Байтотии организовал масштабную реформу имён своих подданных. Имена жителей Байтотии исторически часто содержат повторяющиеся фразы и Байтазар хочет с одной стороны упростить имена, а с другой, сохранить традиции повторения, а именно Байтазар хочет заменить каждое из имён в Байтотии на имя такой же длины, чтобы при этом множества периодов для старого и нового имён совпали, но имя при этом состояло только из символов «0» и «1». Из всех кандидатов в новое имя Байтазар хочет выбрать лексикографически минимальное.

Натуральное число \(k\) (\(1 \le k \lt n\)) называется периодом строки \(s\) длины \(n\) тогда и только тогда, когда для любого натурального \(i\), такого что \(1 \le i \le n - k\), верно что \(s_i = s_{i + k}\).

Множество периодов для данной строки \(s\) – множество таких чисел \(i\), что \(i\) является периодом \(s\). Обозначим его за Per(\(s\)). К примеру, Per(«ABIABUABIAB») = {6, 9}, Per(«0000») = {1, 2, 3}.

Помогите Байтазару перевести имена его подданных, и, возможно, он разрешит вам сохранить ваше собственное имя!