Сегодня 23 Февраля, поэтому Малыш решил устроить парад своих солдатиков. Он уже достал их из коробки, расположил в одну линию и теперь хочет построить их по росту в порядке невозрастания слева направо.

В честь праздника Малыш решил, что будет менять местами тех и только тех солдатиков, между которыми стоят ровно \(2\) или ровно \(3\) других солдатика.

Малышу совершенно не обязательно построить солдатиков за минимально возможное количество перестановок, но ему обязательно нужно это сделать не более чем за \(23\,000\) перестановок, иначе он не успеет до сна.

Помогите Малышу справиться с этой ответственной задачей.

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

Экономический отдел предоставил вашему другу прогноз пассажиропотока на следующие \(n\) часов. Теперь необходимо составить расписание маршруток, а именно для каждого часа определить, выйдет маршрутка на линию в этот час или нет. Известно, что если в \(i\)-ый час на маршрут выйдет маршрутка, то она принесет прибыль ai рублей, при этом ai может быть как положительным, так и нулевым или отрицательным. Также, в связи с ограниченным размером автопарка и в соответствии с требованиями департамента транспорта, маршрутки должны работать примерно \(2/3\) всего времени. Более формально, для любого \(i\) (\(1 \le i \le n\)) величина

\(\)b = \frac{t_{work}}{2} - t_{skip}\(\) должна лежать в пределах от \(−k\) до \(k\) включительно. Здесь \(t_{work}\) — количество часов до \(i\)-ого включительно, в которые маршрутки выходили на линию, а \(t_{skip}\) — количество часов до i-ого включительно, в которые маршрутки не выходили на линию. Помогите вашему другу найти максимальную суммарную прибыль маршрута с учетом всех требований.

У Васи на кухне висят часы с кукушкой. Часы устроены так: в каждый ровный час кукушка кукует столько раз, сколько сейчас часов (от 1 до 12), например, ровно в 7:00 кукушка кукует 7 раз.

Кроме того, в 30 минут каждого часа (в 0:30, 1:30, 2:30 и т.д.) кукушка кукует ровно один раз. Васе очень нравится смотреть на то, как кукует кукушка, он любит считать, сколько раз она прокуковала. Но, к сожалению, сегодня мама отправила Васю в магазин за покупками, и поэтому он пропустил несколько моментов, в которые куковала кукушка. Определите, сколько раз всего куковала кукушка за время отсутствия Васи.

Считайте, что кукушка кукует очень быстро. Например, даже в 11:00 она успевает прокуковать 11 раз быстрее, чем за одну минуту, т.е. к моменту 11:01 кукушка уже закончила куковать.

Вася прошел на уроке математики в школе операцию деления с остатком. Чтобы закрепить пройденный материал, он решил потренироваться в выполнении этого действия. Придя домой, Вася попросил маму назвать \(N\) произвольных натуральных чисел \(X_i\) (\(1 \le i \le N\)), не превосходящих \(10^9\). Затем он придумал некоторое натуральное число \(M\), не превосходящее наибольшего из \(X_i\), и вычислил остатки \(Y_i\) от деления всех чисел на него.

Вечером к Васе зашел его друг Леша и увидел результаты вычислений. Подумав несколько минут, он радостно сообщил товарищу, что придумал еще одно значение \(M\), удовлетворяющее всем соотношениям. Вася был шокирован. Он не мог поверить, что это возможно, и обратился к Вам с просьбой о помощи.

Помогите Васе найти все возможные значения \(M\), удовлетворяющие всем соотношениям.

Несмотря на то, что и Вася, и его друг Леша — прилежные и умные ученики, они могли ошибиться в вычислениях, и ни одного подходящего \(M\) может не существовать.

Миша изучает работы по расшифровке древнеберляндских текстов. Древние берляндцы пользовались иероглифичной письменностью. Поскольку число иероглифов очень велико, в трудах, изучаемых Мишей, каждый иероглиф записывается в виде последовательности строчных латинских символов. Древнеберляднское слово представляет собой последовательность из одного или нескольких иероглифов, записанных один за другим слева направо без разделителей. Известно, что древние берляндцы очень любили палиндромы, поэтому все древнеберляндские слова являются палиндромами: первый иероглиф слова совпадает с последним, второй иероглиф — с предпоследним и так далее.

К сожалению, Миша не нашел правила сопоставления иероглифов последовательностям латинских символов, поэтому чтение трудов дается ему очень тяжело. Отчаявшись найти эти правила, Миша решил попробовать сам угадать разбиение слов на иероглифы, для чего он придумал следующий алгоритм: он выписывает каждое отдельное слово и пытается разбить его на наибольшую по длине последовательность иероглифов так, чтобы эта последовательность при объединении давала исходное слово и при этом являлась палиндромом. Но поиск такого разбиения оказался слишком сложным для Миши, поэтому он обратился за помощью к Вам.