Фонд изучения дикой природы в течение \(t\) лет ежегодно выделяет денежные гранты в поддержку исследований северной фауны. На гранты претендуют три организации, одна из которых занимается изучением тюленей, вторая — оленей, третья — белых медведей.

Для упрощения бухгалтерского учёта фонд принял следующие решения:

• размер любого гранта в денежных единицах должен быть степенью числа 2, то есть равен \(2^k\) для некоторого целого \(k \ge 0\);

• все гранты, получаемые одной организацией в одном году, должны иметь различные размеры.

В \(i\)-м году фонд планирует полностью распределить \(n_i\) денежных единиц, выделенных на гранты. Сравнивать результативность использования средств возможно только для грантов одинакового размера, выделенных каждой из трёх организаций. Такие гранты называются целевыми. Распределение денежных единиц на гранты между тремя организациям считается оптимальным, если как можно б´oльшая часть общей суммы выделена на целевые гранты.

Например, если в текущем году на все гранты выделено 47 денежных единиц, то оптимальным вариантом распределения будет: выделить каждой из организаций целевые гранты размерами по 2 и 8 денежных единиц, что составит в сумме 30 единиц. Остальные 17 единиц можно распределить, например, выделив первой организации 16 денежных единиц, а третьей — 1 денежную единицу. Выделить более 30 денежных единиц на целевые гранты, распределяя 47 денежных единиц, нельзя.

Требуется написать программу, которая по заданной в \(i\)-м году общей сумме грантов \(n_i\) определяет, сколько денежных единиц следует выделить каждой из трёх организаций при оптимальном распределении грантов.

Более формально (будущим участникам заключительного этапа дальше не читать :) ), требуется найти такие три числа \(a\), \(b\) и \(c\), что \(a+b+c=n\), при этом требуется максимизировать \(a \& b \& c\), где "&" обозначает побитовое <<И>>.

Подводная лодка легла на грунт на мелководье. Для её обнаружения используются данные спутника, который с высокой точностью измеряет отклонение высоты поверхности воды от среднего уровня моря. Снимок, получаемый со спутника, представляет собой массив из \(h\) строк по w элементов в каждой строке.

• «корпус» — полоса из элементов с координатами от \((x_1, y_1)\) до \((x_2, y_1)\), где \(x_1 \lt x_2\);

• «рубка» — полоса из элементов с координатами от \((x_3, y_1)\) до \((x_3, y_2)\), где \(x_1 \le x_3 \lt x_2; y_1 \le y_2\);

• «хвост» — полоса из элементов с координатами от \((x_4, y_3)\) до \((x_4, y_4)\), где \(x_3 \lt x_4 \le x_2; y_3 \le y_1 \le y_4\). Поскольку подводная лодка находится вблизи поверхности в районе с сильным течением, уровень воды над ней немного повышается. Поэтому изображением подводной лодки на снимке будем считать потенциальное изображение с максимально возможной суммой входящих в него элементов массива.

Требуется написать программу, которая находит на снимке изображение подводной лодки и выводит сумму его элементов.

Улицу Подводный канал освещают \(n\) фонарей, пронумерованных вдоль улицы от 1 до \(n\). Один или несколько подряд стоящих фонарей назовём сегментом. Таким образом, общее количество сегментов равно \(n(n+1)/2\) . Сегмент считается исправным, если лампочки во всех фонарях этого сегмента исправны.

С фонарями регулярно происходят события одного из двух типов:

• в каком-то сегменте из-за скачков напряжения все лампочки одновременно перегорают;

• Архиэнерго выбирает некоторый сегмент и посылает ремонтников, чтобы заменить на нем все перегоревшие лампочки на исправные.

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

Требуется написать программу, определяющую количество сегментов после каждого события, которые исправны в этот момент или были исправны когда-либо до этого события.

Подземный бункер состоит из \(n\) комнат, соединённых \(n − 1\) коридорами. Каждый коридор соединяет две различные комнаты и имеет определённую длину. Бункер устроен таким образом, что из любой комнаты \(i\) можно дойти в любую другую комнату \(j\). Заметим, что существует единственный такой путь, не проходящий по одному и тому же коридору дважды. Сумма длин коридоров, составляющих этот путь, называется расстоянием между комнатами \(i\) и \(j\) и обозначается \(ρ(i, j)\).

Каждая комната бункера оборудована звуковой сигнализацией, состоящей из сирены и датчика звука, который её включает. Сирена, включённая в комнате \(i\), активирует датчик звука в каждой комнате, рас- стояние до которой не превосходит расстояние \(d_i\) , определяемое мощностью этой сирены. Другими словами, включение сирены в комнате \(i\) автоматически включает сирену во всех комнатах \(j\), таких что \(ρ(i, j) \le d_i\) . Эта сирена, в свою очередь, может вызвать автоматическое включение других сирен и так далее.

В случае возникновения чрезвычайной ситуации некоторые сирены необходимо включить вручную, после чего звук от них автоматически включит сирены в других комнатах. Правила безопасности предписывают выбор такого набора сирен для ручного включения, который в конце концов приведёт к автоматическому включению сирен во всех комнатах.

Требуется написать программу, которая определяет минимальное количество сирен в наборе, удовлетворяющем правилам безопасности.