Четыре Всадника проникают в сейф, где хранятся драгоценности. В сейфе лежат $$$n$$$ слитков золота массами $$$a_1, a_2, ..., a_n$$$.

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

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

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

Четвёрка легендарных иллюзионистов — Всадники — готовит новое выступление. На этот раз их цель — взломать таинственный криптографический сейф корпорации «Arcana». Сейф защищён древним числовым ритуалом: говорят, что только тот, кто сможет подобрать $$$k$$$ различных ключей, откроет замок.

На лицевой панели сейфа высвечивается формула:

Система принимает только натуральные числа $$$a$$$, $$$b$$$, $$$c$$$. Каждый набор ($$$a,\ b,\ c$$$), удовлетворяющий уравнению, считается действующим «магическим ключом». Чтобы открыть сейф, вам нужно сгенерировать k таких ключей.

Долгожданное возвращение «Четырёх всадников»! Атлас, Джек Уайлдер и остальные мастера обмана готовят новый невероятный трюк. На этот раз цель – не обогнать полицию, а обмануть математическую реальность.

На столе у героев лежат два числа $$$n$$$ и $$$m$$$. Их задача – собрать из чисел Фибоначчи $$$F_0, F_1, F_2, \dots$$$ последовательность $$$F_{a_1}, F_{a_2}, \dots, F_{a_k}$$$ ($$$a_1 \leq a_2 \leq \dots \leq a_k$$$), которая должна быть одновременно частью двух трюков

• Трюк Атласа: $$$F_{a_1} \oplus F_{a_2} \oplus \dots \oplus F_{a_k} = n$$$
• Трюк Джейка: $$$F_{a_1} + F_{a_2} + \dots + F_{a_k} = m$$$

Здесь $$$F_0 = 1, F_1 = 1, F_i = F_{i-1} + F_{i-2}$$$ — последовательность Фибоначчи, их секретное оружие. Обратите внимание, что числа в выбранной последовательности не обязаны быть различными — то есть, можно брать одно число Фибоначчи несколько раз.

Ваша миссия — найти минимальное число элементов $$$k$$$, которое позволит всадникам показать этот фокус публике. Если это невозможно — значит, план сорвался, и фокус не удался.

Во время грандиозного шоу иллюзионистов город из $$$n$$$ сцен соединён системой секретных ходов. Каждая сцена — это вершина, каждый ход между двумя сценами — это ребро. Всего ходов $$$n-1$$$, и вместе они образуют дерево.

На каждом ребре написано число $$$w$$$ — «сила иллюзии», с которой зритель переносится между двумя сценами.

Рассмотрим любой маршрут шоу — последовательность различных сцен $$$$$$u_1, u_2, \dots, u_k$$$$$$ где $$$k \geq 2$$$ и соседние сцены соединены прямым секретным ходом. Такой маршрут не может самопересекаться (одна и та же сцена не может появляться более одного раза).

Красотой маршрута назовём XOR всех сил иллюзий на этом пути:

$$$$$$w_{u_1 \rightarrow u_2} \oplus w_{u_2 \rightarrow u_3} \oplus \dots \oplus w_{u_{k - 1} \rightarrow u_k}.$$$$$$

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

Команда «Всадников» готовит финальный трюк своего шоу — синхронизированное проникновение в защищённый дата-центр во время прямого эфира.

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

В любой момент времени Всадники могут сделать следующее:

• Взять шнур, который не горит, и поджечь его с одной или двух сторон.
• Взять шнур, который горит с одной стороны, и поджечь его с другой или потушить.
• Взять шнур, который горит с двух сторон, и потушить его с одной или двух сторон.

Причём в один момент времени они могут совершать несколько действий с разными шнурами.

Всадникам известно, что $$$i$$$-й шнур сгорит ровно за $$$t_i$$$ секунд, если поджечь его с одной стороны; если же шнур горел $$$x$$$ секунд с одной стороны, а потом Всадники решат поджечь его с другой, то ему останется гореть $$$\frac{t_i-x}{2}$$$ секунд. Шнуры горят неравномерно, поэтому по их длине невозможно определить, сколько времени прошло с поджога.

Определите, можно ли отмерить время, равное $$$T$$$, если считать, что шоу начнется, как только они зажгут или затушат какой-то из шнуров.

Легендарные Четыре Всадника готовят для своего выступления трюк под названием «Вечный двигатель». Для его реализации они создали механизм, представляющий собой выстроенные в ряд $$$n$$$ шестерёнок с различным количеством зубьев $$$a_1, a_2, ..., a_n$$$.

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

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

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

Рассмотрим динамическое множество команд иллюзионистов. Каждая команда с номером $$$i$$$ характеризуется двумя параметрами $$$x_i$$$ и $$$k_i$$$ (обратите внимание, что оба параметра у двух разных команд могут совпадать).

Начиная с дня $$$t = 1$$$, команда живёт по бесконечному циклу:

• в течение первых $$$k_i$$$ дней команда активно выступает с интенсивностью $$$x_i$$$;
• затем следующие $$$k_i$$$ дней команда полностью исчезает, готовя новые фокусы и не внося никакого вклада в общую «интенсивность магии».

Затем цикл повторяется: $$$k_i$$$ дней выступлений, $$$k_i$$$ дней тишины, и так далее.

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

Поддерживаются три типа запросов:

1. + $$$x$$$ $$$k$$$ — на сцену выходит новая команда иллюзионистов с параметрами $$$x$$$ и $$$k$$$;
2. - $$$x$$$ $$$k$$$ — команда с параметрами $$$x$$$ и $$$k$$$ прекращает участвовать в игре;
3. ? $$$t$$$ — требуется узнать суммарную интенсивность всех команд в день с номером $$$t$$$.

Помогите наблюдателям узнавать ответы на все запросы третьего типа.

На плоскости расставлены $$$n$$$ магических меток, $$$i$$$-я метка изначально имеет координаты ($$$x_i; y_i$$$). Затем Джесси делает с ними $$$q$$$ трюков. Каждый трюк описывается пятью числами $$$l$$$, $$$r$$$, $$$x$$$, $$$y$$$, $$$a$$$ ($$$a \in [90, 180, 270]$$$). Джесси поворачивает все метки на позициях с $$$l$$$-й по $$$r$$$-ю относительно точки ($$$x; y$$$) на $$$a$$$ градусов по часовой стрелке.

После каждого фокуса Джесси нужно накрывать все метки специальным прямоугольным полотном для следующего фокуса. При чём стороны прямоугольника должны быть параллельны осям координат. Вам нужно определить, чему равна минимальная площадь подходящего полотна после каждого фокуса. Гарантируется, что после каждого фокуса абсолютное значение координат меток не превышает $$$10^9$$$.

Настало время для финального шоу «Четырёх всадников»! Специально для него был подготовлен фокус, который никто и никогда раньше не видел.

Чтобы создать такой фокус, «Всадники» записали все трюки из своих предыдущих выступлений в виде строки $$$s$$$. Всего у них в арсенале $$$n$$$ трюков, которые они могли использовать в своих шоу. Они обозначаются первыми $$$n$$$ строчными буквами латинского алфавита; в $$$s$$$ же использованы лишь некоторые из них (но, может быть, и все).

Они хотят быть уверены, что выбранная для нового фокуса последовательность трюков действительно новая. Для этого она не должна встречаться в строке $$$s$$$ как подпоследовательность — то есть её нельзя получить из $$$s$$$, вычёркивая некоторые символы.

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

«Четыре Всадника» ищут минимальную длину $$$k$$$, при которой существует последовательность из $$$k$$$ трюков их арсенала, не являющаяся подпоследовательностью $$$s$$$. Помогите им найти её.

Четверо Всадников готовят новый трюк. На сцене перед зрителями стоит магическая доска, на которой изначально записано одно число $$$S$$$ — сумма денег, которая якобы лежит в банковской ячейке.

За один ход маги могут выполнить следующий «номер»:

• выбрать какое-то число $$$y$$$, записанное на доске;
• стереть $$$y$$$;
• вместо него записать два натуральных числа $$$a$$$ и $$$b$$$ такие, что $$$y = a + b$$$.

Однако за каждый такой размен продюсеру приходится платить за спецэффекты $$$a \cdot b$$$ монет.

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

Дан массив из $$$n$$$ чисел $$$x_1, x_2, \dots, x_n$$$ — потенциальные финальные суммы для разных вариантов трюка.

Продюсер задаёт $$$q$$$ вопросов. Каждый вопрос описывает одну постановку:

• выбирается подотрезок массива $$$x$$$ — от $$$l$$$ до $$$r$$$;
• задаётся исходная сумма на доске $$$S$$$.

Для каждого такого запроса нужно определить, можно ли, начиная с единственного числа $$$S$$$ на доске, с помощью описанных действий получить набор чисел $$$x_l, x_{l+1}, \dots, x_r$$$ (порядок не важен, на доске могут быть дополнительно другие числа). Если можно — сообщить, какова минимальная суммарная стоимость всех разменов в монетах, необходимая для реализации такого трюка; иначе — сообщить, что трюк невозможен.

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

В защитном модуле есть набор из $$$n$$$ слов, состоящих из строчных латинских букв. Джек быстро понял, что для взлома достаточно написать какие-то $$$k$$$ слов из набора, причём слова могут повторяться, а после каждого слова, кроме последнего, должен идти пробел (пробелы печатаются отдельным пальцем, так что на их написание время не тратится). Чтобы написать какую-то букву, Джек должен переместить палец с текущей кнопки на другую кнопку, при чём он тратит на это действие время, равное расстоянию между начальной и конечной кнопками. Время на нажатие кнопки, на которой находится палец, не тратится.

Клавиатура задана тремя строками длины 9. На ней есть все буквы латинского алфавита, а также один пробел. Расстояние между кнопками считается как сумма абсолютной разницы координат кнопок (то есть чтобы из кнопки ($$$x_1;\ y_1$$$) дойти до кнопки ($$$x_2;\ y_2$$$), нужно потратить $$$|x_2 - x_1| + |y_2 - y_1|$$$ единиц времени).

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