Давным давно Шамиль и Вадим долгое время не могли решить, кто главный фанат JoJo, поэтому они решили устроить дуэль. К счастью, дуэль была не на пистолетах, а победитель решался в данной игре:

Игра начинается с жеребьевки, в ходе которой Шамилю и Вадиму достаётся $$$a$$$ и $$$b$$$ монет соответственно. На столе стоял наполненный стакан воды, и игроки по очереди (начиная с Шамиля) бросали туда свои монеты. Если у игрока не осталось монет, он пропускает свой ход. Игра оканчивалась, когда у Шамиля и Вадима кончались монеты или вода выливалась. Победителем объявлялся тот, на чьем последнем ходу не пролилась вода. По стечению обстоятельств в тот день игра окончилась при броске последней монеты.

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

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи успешно пройдены.

Совсем недавно стало известно, что существуют стенды (физические проявления духовной силы пользователя), которые могут работать без участия человека. Одним из таких стендов стал Natarius S.M.A.L.L, обнаруженный в глубинах океана.

Оказалось, что он способен воспроизводить(копировать) самого себя и структура популяции тесно связана с треугольниками. Исследователям даже удалось выяснить алгоритм их распространения. Процесс роста популяции Natarius S.M.A.L.L происходит по следующим шагам:

1. На первом шаге появляется первая группа, состоящая из одной особи, которая имеет форму треугольника.
2. На каждом следующем шаге $$$i$$$ в местах, где граница группы оставалась пустой, возникают новые группы, каждая из которых состоит из $$$i$$$ особей.

Ученые заинтересовались данным стендом, но были НЕВЕРОЯТНО ленивы, и обратились к вам с просьбой: рассчитать численность популяции Natarius S.M.A.L.L на шаге $$$n$$$. Чтобы избежать работы с НЕВЕРОЯТНО большими числами, результат необходимо вычислить по модулю $$$2027$$$.

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

Совсем недавно некий Z.Джалиль узнал, что в день рождения одного из его друзей проходит мероприятие под названием ДжоДжоДень!!! Z.Джалиль тоже захотел, чтобы в его день рождения какой-нибудь мангака устроил похожее мероприятие. Так как он очень деятельный человек, то решил не ждать, а сам стать мангакой и организовать тематический праздник в день своего рождения. Публиковать мангу он решил в Weekly Shonen Jump, то есть каждую неделю он должен выпускать новую главу. Однако редактор разрешил ему взять не более $$$k$$$ каникул, и все каникулы должны длиться одинаковое количество дней.

Кроме того, один его друг нагадал ему на картах Таро, что для того чтобы стать популярным к своему дню рождения, он должен выпустить не меньше $$$r$$$ глав своей манги.

Теперь он планирует свои действия. У него есть два варианта:

1. Всю неделю работать над новой главой (то есть за 7 дней выпустить новую главу).
2. Поехать в путешествие в тихий городок Морио к своему другу Кире на w дней, вдохновиться и выпустить новую главу за один день работы (то есть отдыхать $$$w - 1$$$ день и выпустить главу на $$$w$$$-й день).

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

После написания новой НЕВЕРОЯТНОЙ главы своей НЕВЕРОЯТНОЙ манги, Z.Джалиль для вдохновения отправился к своему другу Й.Кире в тихий городок Морио. Там он вместе с ним отправился в НЕВЕРОЯТНЫЕ душевые города Морио. Душевая представляет собой помещение из $$$n$$$ отдельных кабинок тропических душей. В каждой такой кабинке можно настроить температуру, однако злобный Ik.Bilin своим стендом "Despacito" связал все души. Джалиль выяснил некоторые закономерности в работе душевой:

1. Температура воды в $$$i$$$ душе измеряется в $$$a_i$$$ градусов по Самату (значения в градусах по Самату измеряются в целых неотрицательных числах);
2. Если в $$$i$$$ кабинке температура установлена на $$$t_i$$$ ($$$0 \le t_i$$$) градусов, то температура в данной кабинке вырастет на $$$t_i$$$ градусов, а в остальных кабинках вырастет на $$$\frac{t_i}{2}$$$ (то есть, если массив $$$t = [0, 4, 0, 0]$$$, то массив $$$a$$$ будет равен $$$[2, 4, 2, 2]$$$, или если $$$t = [6, 0, 4, 0]$$$, то $$$a = [8, 5, 7, 5]$$$ и т.д.);
3. Температура включеная в каждой кабинке всегда кратна 2 (то есть $$$t_i$$$ всегда делится на 2);

Заметьте, $$$t_i$$$ — это не температура воды в $$$i$$$-й кабинке, а то, насколько температура воды установленна в самой кабинке непосредственно. Так как кабинки душевой влияют друг на друга, температура в $$$i$$$-й кабинке равна $$$a_i$$$ (Если до сих пор не понятно перечитайте условие!).

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

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

Самат, герой вселенной, где обитают духи, столкнулся со сложной миссией — победить злого духа, терроризирующего этот мир уже более трёхсот лет. Самат почти одержал победу, но в последний момент злой дух применил свой коронный приём: бросок n десятигранных костей.

Этот бросок увеличивает характеристики духа. Характеристики духа увеличиваются на количество непрерывных отрезков костей $$$[l; r]$$$, где наибольший общий делитель элементов массива с позиции $$$l$$$ по $$$r$$$ — НОД$$$(a_l,a_{l+1},...,a_{r-1},a_r)$$$ равен 1, а сумма крайних элементов $$$a_l + a_r = k$$$.

Операция НОД$$$(b_1,b_2,...,b_k)$$$ примененная к $$$k$$$ числам вычисляется как последовательное вычисление наибольшего общего делителя элементов массива $$$b$$$. Например:

• НОД$$$(2,4,3)$$$ = 1, так как наибольший общий делитель чисел 2 и 4 равен 2, а чисел 2 и 1 равен 1.
• НОД$$$(6,9,3)$$$ = 3, так как наибольший общий делитель чисел 6 и 9 равен 3, а чисел 3 и 3 равен 3.
• НОД$$$(6,12,3)$$$ = 3, так как наибольший общий делитель чисел 6 и 12 равен 6, а чисел 6 и 3 равен 3.

Теперь дух стал сильнее, и Самат хочет узнать, нужно ли вызывать помощь. Ему известны числа, выпавшие на костях. Самат передал вам результат бросков в виде массива $$$a$$$ длины $$$n$$$ и просит вас посчитать, насколько усилился дух.

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

Совсем недавно Карам стал директором школы, но какой же может быть директор без своей печати? Поэтому Карам решил заказать себе с RiliExpress $$$n$$$ печатей, $$$i$$$-я из которых представляет собой матрицу $$$h_i$$$ на $$$w_i$$$, где в некоторых клетках есть краска.

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

Караму стало интересно, что будет, если каждую из печатей применить $$$x_i$$$ раз в позициях $$${0, 1,..., x_i - 2, x_i-1}$$$. После этого он захотел узнать, сколько клеток покрашены. Для понимания процесса применения печатей посмотрите примечания к примерам.

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

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

Карам создал метрику, по которой он будет оценивать рассадку в кабинете. А именно:

1. Каждая парта получила свою ценность $$$a_i$$$, если за этой партой будет сидеть ребёнок, то оценка рассадки будет увеличена на $$$a_i$$$.
2. Карам не очень любит, когда дети списывают, поэтому он за каждую пару детей, сидящих рядом, будет уменьшать оценку рассадки на $$$C$$$.

Карам хочет узнать максимально возможную ценность рассадки в кабинете.

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