Крош и Ёжик собрали для Совуньи $$$n$$$ грибов. Для их засолки Совунья подготовила $$$k$$$ банок и хочет разложить грибы поровну в каждую из них.

К сожалению, количество собранных грибов $$$n$$$ может не делиться нацело на число банок $$$k$$$. Совунья не хочет выбрасывать грибы, поэтому просит Кроша и Ёжика принести ещё немного. Однако, чтобы не перетруждать друзей, она хочет попросить как можно меньше дополнительных грибов.

В задаче $$$20$$$ тестов, каждый из которых оценивается в $$$5$$$ баллов.

Решения, корректно работающие для $$$1 \le n, k \le 10^5$$$, получат не менее $$$50$$$ баллов.

Пин, гениальный изобретатель из Ромашковой долины, снова что-то мастерит. На этот раз он создал новый механизм для Биби и назвал его «Числовые шестерёнки». Сердце механизма — две пары шестерёнок, которые нужно соединить особым образом. Пин экспериментальным путём выяснил, что механизм запустится, если у двух соединённых пар совпадают их гармонические числа.

У Пина есть четыре шестерёнки, на каждой из которых написано одно число: на первой шестерёнке — $$$a$$$, на второй — $$$b$$$, на третьей — $$$c$$$ и на четвёртой — $$$d$$$.

Гармоническое число упорядоченной пары шестерёнок $$$(x, y)$$$ (где $$$y \neq 0)$$$ — это остаток от деления $$$x$$$ на $$$y$$$. Например, для пары $$$(7, 3)$$$ гармоническое число равно $$$1$$$, так как $$$7 \bmod 3 = 1$$$.

Порядок в паре важен: для пары $$$(7, 3)$$$ гармоническое число равно $$$1$$$, а для пары $$$(3, 7)$$$ — $$$3$$$.

Помогите Пину понять, сможет ли он запустить механизм, используя эти четыре шестерёнки.

Оценка складывается из баллов за пройденные тесты. За каждый правильно пройденный тест вы получаете $$$2$$$ балла.

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

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

По записям за $$$N$$$ дней определите, сколько всего часов и минут проспал Крош за это время.

В задаче потестовая оценка: за каждый пройденный тест начисляется 5 баллов.

Во время очередной экспедиции в пустыню Крош и Ёжик наткнулись на загадочную глиняную табличку, покрытую древними знаками. Поверхность таблички была аккуратно расчерчена на сетку из $$$N$$$ строк и $$$M$$$ столбцов. Некоторые клетки таблицы были закрашены. Друзья догадались, что каждый прямоугольник $$$5 \times 3$$$ может скрывать какую-то цифру от $$$0$$$ до $$$9$$$. Пример представления цифр (звёздочки обозначают закрашенные клетки, а точки — незакрашенные):

0: ***  1: ..*  2: ***  3: ***  4: *.*
   *.*     ..*     ..*     ..*     *.*
   *.*     ..*     ***     ***     ***
   *.*     ..*     *..     ..*     ..*
   ***     ..*     ***     ***     ..*

5: ***  6: ***  7: ***  8: ***  9: ***
   *..     *..     ..*     *.*     *.*
   ***     ***     ..*     ***     ***
   ..*     *.*     ..*     *.*     ..*
   ***     ***     ..*     ***     ***

Но, как это часто бывает с древними артефактами, всё оказалось не так просто! Похоже, авторы таблички (возможно, шумеры, а может, просто очень взволнованный кактус) в спешке закрасили лишние клетки.

Крош и Ёжик подумали и решили, что прямоугольник $$$5\times 3$$$ содержит цифру $$$d$$$, если все клетки, которые должны быть закрашены у цифры $$$d$$$, действительно закрашены на табличке. А если где-то добавились лишние звёздочки — ничего страшного! Главное, чтобы ничего не пропало.

Например, прямоугольник:

***
.**
***
**.
***

А что, если прямоугольник подходит сразу под несколько цифр? Тогда выберем самую большую! — решили Крош и Ёжик. Например, прямоугольник:

***
***
***
..*
***

подходит и под $$$1$$$, и под $$$3$$$, и под $$$5$$$, и даже под $$$9$$$. Но поскольку $$$9$$$ — самая большая из них, именно $$$9$$$ и будет записана в ответ.

Важно! Цифры не могут быть перевернуты и всегда расположены вертикально.

Теперь друзья хотят узнать: чему равна сумма всех цифр, закодированных в табличке?

Для этого нужно рассмотреть все возможные позиции прямоугольника $$$5\times 3$$$, которые полностью помещаются в таблицу — двигая его по строкам сверху вниз и по столбцам слева направо, как будто «скользя» по поверхности. Прямоугольники могут пересекаться — это не разбиение на блоки, а именно все возможные окна размером $$$5\times 3$$$.

Если в каком-то окне не получается распознать ни одну цифру, оно просто ничего не добавляет к сумме.

Помогите Крошу и Ёжику расшифровать древнее число!

В задаче 50 тестов, каждый оценивается на 2 балла. Тесты разбиты на 3 группы, внутри каждой группы действует потестовая оценка, то есть баллы начисляются за каждый тест независимо. Группа 3 тестируется, только если все тесты первой и второй группы были пройдены.

Нюша — большая модница и поклонница косметики. В её коллекции сотни баночек с пудрами, помадами и кремами. Перед каждой прогулкой с Барашем она наносит макияж, чтобы подчеркнуть свою элегантность.

Как известно любой моднице, не все косметические средства хорошо сочетаются друг с другом. Чтобы навести порядок в своей огромной коллекции, Нюша расставила всю косметику в один длинный ряд. Каждой баночке $$$i$$$ она сопоставила целое число $$$a_i$$$ — числовую характеристику её стиля.

Нюша придумала особое правило для оценки сочетаемости средств: для любого набора баночек она вычисляет так называемое магическое число — результат операции XOR ($$$\oplus$$$, побитовое исключающее ИЛИ) над всеми числами в этом наборе.

Что такое XOR?

XOR — это особая операция над числами. Чтобы её выполнить, нужно:

• записать числа в двоичной системе (с одинаковым числом цифр, добавляя нули слева при необходимости);
• в каждом разряде сравнить цифры:
  • если цифры одинаковые ($$$0$$$ и $$$0$$$ или $$$1$$$ и $$$1$$$) — пишем $$$0$$$;
  • если разные ($$$0$$$ и $$$1$$$) — пишем $$$1$$$.

Например:

Для трёх и более чисел XOR вычисляется по шагам: сначала XOR первых двух, потом XOR результата с третьим и так далее.

В большинстве языков программирования операция XOR записывается с помощью символа «крышка». Например, в Python, C++ или Java выражение a ^ b означает побитовое исключающее ИЛИ чисел a и b.

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

Нюша хочет рассмотреть все возможные подотрезки (все способы выбрать подряд идущие баночки), вычислить магическое число для каждого из них, а затем найти XOR всех этих магических чисел. Помогите Нюше найти это итоговое число!

В задаче 50 тестов, каждый оценивается на 2 балла. Тесты разбиты на 3 группы, внутри каждой группы действует потестовая оценка, то есть баллы начисляются за каждый тест независимо. Зависимости между группами тестов указаны в таблице ниже