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

Программист Лев из VK обычно справляется со всеми поставленными задачами заранее, но в этот раз слишком долго откладывал последнее дело, и планирует закончить его этой ночью. Чтобы оставаться бодрым, ему необходимо минимум $$$x$$$ кофеина. Для этого он собирается собрать комплект из кофейных снеков, всегда доступных в офисе.

Всего доступно $$$n$$$ снеков, $$$i$$$-й из которых присутствует в наличии в массе $$$m_i$$$ и с долей содержания кофеина $$$k_i \%$$$. При этом $$$i$$$-й из снеков имеет тип (напиток, печенье, шоколадный батончик, и т. д.), характеризующийся целым числом $$$t_i$$$.

Смешивать снеки разных типов плохо, поэтому Лев хочет обойтись как можно меньшим количеством разных типов снеков. Помогите ему выбрать такой набор снеков, суммарная масса кофеина в котором хотя бы $$$x$$$, а количество различных типов снеком минимально.

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

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

Дробь с периодом записывается в формате $$$a.b(c)$$$, что соответствует $$$a.bccc\ldots$$$, где $$$c$$$ повторяется бесконечное число раз. Например, $$$1.25(13)$$$ задает число $$$$$$1 + \tfrac{2}{10} + \tfrac{5}{10^2} + \tfrac{1}{10^3} + \tfrac{3}{10^4} + \tfrac{1}{10^5} + \tfrac{3}{10^6} + \ldots$$$$$$

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

Число представляется в виде непериодичной дроби в системе счисления с основанием $$$c$$$, если оно представимо в виде конечной суммы $$$\sum\limits_{i} \frac{a_i}{c^i}$$$. В частности, мы считаем, что для целого числа ответом на задачу будет $$$c = 1$$$.

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

Проект нового города предполагает застройку в виде решетки размером $$$n \times m$$$ клеток. На пересечении $$$i$$$-й строки и $$$j$$$-го столбца будет располагаться дом на $$$t_{i,j}$$$ жильцов.

Три дома в клетках $$$(i, j)$$$, $$$(i + a, j)$$$ и $$$(i, j + b)$$$ образуют хороший треугольник, подходящий для линии общественного транспорта, если:

• $$$a \gt 0$$$ и $$$b \gt 0$$$;
• в доме $$$(i, j)$$$ живет ровно $$$a + b$$$ жильцов;
• в доме $$$(i + a, j)$$$ живет ровно $$$b$$$ жильцов;
• и в доме $$$(i, j + b)$$$ живет ровно $$$a$$$ жильцов.

Вы можете изменить план застройки, увеличив или уменьшив все $$$t_{i,j}$$$ на одно и то же целое число $$$d$$$. Если $$$t_{i,j}$$$ при этом должно опуститься ниже нуля, считайте его равным нулю. Обозначим за $$$T + d$$$ матрицу значений $$$t_{i,j} + d$$$, а за $$$\triangle(T + d)$$$ — количество хороших треугольников при застройке города соответствующим образом.

Найдите $$$$$$\sum\limits_{d=-\infty}^{+\infty} \triangle(T + d) \text{,}$$$$$$ или, иными словами — суммарное количество хороших треугольников по всем возможным планам застройки.

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

В современном мире есть множество различных баз данных, основанных на разных структурах и принципах. В дополнение к реляционным (например, MySQL) и графовым (например, GraphQL), недавно стажер компании VK предложил идею новой базы данных DequeQL, основанной на деках. Разумеется, не все идеи стажеров действительно хорошие, но, будучи ответственным ментором, Лев решил реализовать его идею и проверить ее эффективность.

Дек — структура данных, хранящая последовательность элементов, и позволяющая добавлять новый элемент или вынимать элемент с любого из двух концов последовательности. Базовым блоком данных в DequeQL является юнит (unit) — пустой дек, соответствующий минимальной единице информации. Сама база данных представляет из себя множество пронумерованных деков, вложенных друг в друга. Дек, не вложенный ни в какой другой, называется корнем. Разумеется, если некоторый юнит не лежит в другом деке, он тоже считается корнем.

DequeQL поддерживает четыре операции на изменение:

1. push_back($$$d_1$$$, $$$d_2$$$) — положить корень $$$d_1$$$ в конец корня $$$d_2$$$ ($$$d_1$$$ перестает быть корнем);
2. push_front($$$d_1$$$, $$$d_2$$$) — положить корень $$$d_1$$$ в начало корня $$$d_2$$$ ($$$d_1$$$ перестает быть корнем);
3. pop_back($$$d$$$) — достать из корня $$$d$$$ последний элемент (при этом этот элемент становится корнем);
4. pop_front($$$d$$$) — достать из корня $$$d$$$ первый элемент (изъятый элемент тоже становится корнем);

Обратите внимание, что операции можно производить только над корневыми элементами базы данных. Лев уже реализовал эти операции, и решил, что DequeQL может быть полезна в одном из новых проектов VK, если расширить ее функционал и добавить поддержку ответов на запрос pop_complexity($$$d$$$) — какое минимальное количество операций pop_back или pop_front надо выполнить, чтобы $$$d$$$ стал корнем? Сама структура базы данных при этом не меняется, то есть выполнять соответствующие действия pop не надо.

Пока у Льва выходной, у вас есть возможность зарекомендовать себя в качестве квалифицированного разработчика. Вам дана база данных, состоящая из $$$n$$$ юнитов с номерами от $$$1$$$ до $$$n$$$. Реализуйте требуемый функционал и выведите ответ на каждый запрос.

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