В лаборатории аномальных материалов антинаучно-исследовательского комплекса «Black Mesa» проводят эксперименты с недавно разработанным графитовым наностержнем. Графитовый наностержень представляет собой \(n\) последовательно соединенных атомов углерода, находящихся на одной прямой. Каждый атом имеет определенный заряд.

Для проведения эксперимента, стержень располагают вертикально. Пронумеруем атомы от 1 до n снизу вверх. Между двумя атомами образуется сильная связь, если это соседние атомы и верхний из них имеет заряд ровно на один больше, чем нижний. Иными словами, атомы a и b соединены сильной связью, если \(a \ = \ b \ + \ 1\) и \(q_a \ = \ q_b \ + \ \)1, где \(q_i\) — заряд \(i\)-го атома. Цепочкой атомов назовем несколько последовательных атомов, соединенных сильными связями.

Вчера был проведен очередной эксперимент. Перед началом эксперимента каждому атому установили определенный заряд: \(i\)-му атому установили заряд \(q_i\).

Во время эксперимента ученые проводили действия двух типов:

• у всех атомов с номерами от \(l_i\) до \(r_i\), включительно, заряд изменяли на величину \(d_i\);
• временно разрушали все сильные связи атомов, кроме тех, которые соединяют атомы с номерами от \(l_i\) до \(r_i\), включительно, и измеряли длину самой длинной цепочки атомов среди оставшихся сильных связей. Затем восстанавливали все временно разрушенные связи.

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

Подруге Ане он личным сообщением в социальной сети сообщил число внутри месяца, а другу Боре — месяц своего рождения. Затем он опубликовал на своей странице список дней года, один из которых — день его рождения, а также фразу о том, что Аня знает число, но не знает месяц, а Боря — знает месяц, но не число.

Затем в комментариях состоялся следующий диалог:

Аня: Я не знаю точную дату рождения Вани, но я уверена, что и Боря её тоже не знает.

Боря: Я сначала не знал дату Ваниного рождения, но теперь, после твоего комментария, знаю точно!

Аня: Ого! Теперь и я тоже знаю точную дату!

Когда же у Вани день рождения?

В кинотеатре «Дружба» через неделю пройдет премьера мирового хита «Осторожный Макс», и шушпанчики обязательно хотят попасть на первый сеанс. Зал в кинотеатре состоит из \(n\) рядов по \(n\) мест в каждом. Ряды пронумерованы от \(1\) до \(n\), места в каждом ряду также пронумерованы от \(1\) до \(n\). Обозначим место с номером \(c\) в ряду \(r\) как \((r, \ c)\).

Шушпанчики точно знают, что лучшее место в зале — место \((r_b, \ c_b)\). Для любого места \((r, \ c)\) можно посчитать неудачность этого места как
\(|r \ − \ r_b| \ + \ |c \ − \ c_b|\), и чем неудачность меньше, тем лучше.

Шушпанчики пойдут на сеанс группой из \(k\) шушпанчиков. Они хотят сидеть рядом друг с другом, поэтому договорились купить \(k\) мест подряд в одном ряду. Таким образом, шушпанчики купят билеты на места \((r_a, \ c_a), \ (r_a, c_a \ + \ 1) \ , \dots, \ (r_a, \ c_a \ + \ k \ − \ 1)\) для некоторых \(r_a\) и \(c_a\).

К сожалению, некоторые места уже забронированы, и их выкупить не получится. Помогите шушпанчикам выбрать \(k\) соседних мест на одном ряду так, чтобы суммарная неудачность выбранных ими мест была минимальна.

Завершилась Командная Интернет-олимпиада Новой Зеландии по Алгоритмам (КИНЗА). После олимпиады оргкомитет принял решение отправить футболки всем призерам олимпиады. Доставка футболок была поручена компании, в которой работает курьер Билл.

Биллу требуется доставить \(n\) футболок. Он должен доставлять посылки в том порядке, в котором они значатся в его обходном листе. При этом, если посылку доставить не удалось, то в обходном листе ставится отказ, и Билл едет по следующему адресу.

Билл начинает свой рабочий день в офисе компании в момент 0. Приезжая к адресату посылки, он ждет не более \(k\) минут, и если за это время адресат открывает дверь, то Билл отдает ему посылку, процесс передачи посылки без учета времени ожидания занимает \(t\) минут. Если же в течение \(k\) минут дверь не открывается и получатель не появляется, то Билл едет дальше. При этом, если получатель появился ровно ровно через \(k\) минут после приезда Билла, то Билл успевает это заметить, и посылка оказывается доставлена. Рабочий день Билла заканчивается, когда он заканчивает передавать последнюю посылку, либо отмечает в обходном листе отказ от ее получения.

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

Сегодня Леша проходил в школе деление столбиком. На дом ему задали вычислить частное двух больших чисел: \(n\) и \(m\). Леша уже попробовал решить пример, но, неожиданно для себя, понял, что \(n\) на \(m\) не делится. Он уверен, что учитель задавал пример, в котором результат не имеет остатка, поэтому он предположил, что допустил ошибку при переписывании примера с доски.

Теперь он хочет исправить несколько цифр в числе \(n\), чтобы оно стало делиться на \(m\). При этом, Леша хочет, чтобы новое число отличалось от записанного у него в минимальном количестве позиций.

Числа, записанные Лешей, не имеют ведущих нулей, он уверен, что числа, записанные на доске, также не имели ведущих нулей, поэтому и в новом числе их не должно быть. Само число 0 при этом является допустимым.

Помогите Леше.