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

Задача решается с помощью следующего жадного алгоритма: наберем в лифт $$$k$$$ людей, которые хотят попасть на самые высокие этажи, очевидным образом отвезти их по своим этажам у нас займет $$$max floor \cdot 2$$$ операций перемещения лифта. Будем отвозить с первого этажа людей таким образом пока они у нас не закончатся.

Можно заметить, что $$$i$$$-е число в массиве входит в сумму $$$i$$$ раз, а значит значение $$$\frac{a_i}{i}$$$ в сумму добавит $$$a_i$$$. То есть перестановка элементов не влияет на искомую сумму и значит достаточно проверить равна ли сумма элементов массива заданному числу.

Сначала заметим, что числа 0 и 1 не являются простыми. Теперь попробуем построить подходящий квадрат из только из этих чисел. Для начала заполним единичками главную и побочную диагональ квадрата.

Если $$$n$$$ чётное, то сумма в каждой строке и каждом столбце равна $$$2$$$(простому числу), и мы выполнили условие задачи.

Если же $$$n$$$ нечётное, то сумма в строке c номером $$$\frac{n+1}{2}$$$ и в столбце с номером $$$\frac{n+1}{2}$$$ будет равна единице. Чтобы это исправить, добавим единички в клетки $$$(\frac{n}{2}, \frac{n+1}{2})$$$ и $$$(\frac{n+1}{2}, \frac{n+1}{2} + 1)$$$. В итоге сумма в столбцах и строках будет равна двум или трём, и мы опять же выполнили условие задачи.

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

Давайте просимулируем работу алгоритма бинарного поиска. Изначально у нас есть требуемая позиция $$$pos$$$. Для очередной позиции $$$middle$$$ в бинарном поиске, мы можем точно определить, должно ли быть очередное число на этой позиции больше или меньше числа $$$x$$$. Для всех остальных позиций значения чисел могут быть как больше, так и меньше числа $$$x$$$.

По итогу симуляции алгоритма, у нас есть $$$cntBig$$$ позиций, на которых числа должны быть больше числа $$$x$$$ и $$$cntLess$$$ позиций, на которых числа должны быть меньше числа $$$x$$$. Пусть больших чисел $$$hasBig$$$, а меньших $$$hasLess$$$. Теперь посчитаем количество способов разместить большие числа в $$$cntBig$$$ позиций по формуле $$$C(hasBig, cntBig) \cdot cntBig!$$$. Аналогично посчитаем для меньших чисел, а произведение получившихся результатов будет являться ответом на задачу.

Вспомним, что площадь трапеция равна сумме оснований умноженное на высоту и деленное на два. Рассмотрим два случая:

• $$$w$$$ находится в основании. Если $$$2 \cdot s > w$$$, то можно взять высоту трапеции равной $$$1$$$ и другое основание как $$$2 \cdot s - w$$$;

• $$$w$$$ находится не в основании. Тогда давайте переберем высоту трапеции $$$h$$$. Она будет является делителем числа $$$2 \cdot s$$$. Для каждой высоты проверим, можно ли получить наклонную длины $$$w$$$ при высоте $$$h$$$ ($$$x^2 + h^2 = w^2$$$) и могут ли при этом основания быть положительными длинам $$$\frac{2 \cdot s}{h} \ge 2$$$. Если так, то можно строить трапецию с основаниями $$$1$$$ и $$$\frac{2 \cdot s}{h} - 1$$$, с высотой $$$h$$$ и нужным наклоном (разница по абсциссе равна $$$x$$$).

Для начала докажем, что идеальным палиндромом являются только строки вида $$$s_1s_2s_1s_2s_1...$$$, причём $$$s_1 \neq s_2$$$. Это так, потому что если мы заменим символ $$$s_1$$$ или $$$s_2$$$, то подстроки длины 3 перестанут быть палиндромами, а если бы $$$s_1$$$ и $$$s_2$$$ были равны, то подстроки длины 2 были палиндромами. Тогда итоговое количество идеальных палиндромов это $$$m \cdot (m - 1)$$$.

Теперь докажем, что все строки, длины большей чем 5, не могут содержать даже одну ошибку. Если ошибка будет в нечётной длине, то она обязательно будет в длине 3 (и соответственно обязательно в длине 5, так как изначальная строка имеет вид $$$s_1s_2s_1...$$$), следовательно ошибки в нечетной стороне быть не может. Аналогично с чётной стороной, если существует ошибка в длине 2 (то есть $$$s_i = s_{i+1}$$$), то вторая ошибка будет либо в длине 3 (если $$$s_{i+2} \neq s_{i+1}$$$), либо в длине 4. Соответственно ошибки в чётной стороне тоже не может быть.

По итогу получаем, что для строк длины большей, чем 5 ответом будет являться число $$$m \cdot (m - 1)$$$, а для меньших строк можно просто запустить перебор.

Давайте считать искомое произведение сумм $$$ans_i$$$ для множеств, наибольший общий делитель элементов которых равен $$$i$$$. Для начало выберем все элементы, которые делятся на $$$i$$$. Чтобы найти только те множества, НОД которых точно равен $$$i$$$, можно найти произведение сумм для всех подмножеств и вычесть ответы всех $$$ans_j$$$ таких, что $$$i < j$$$ и $$$i$$$ делит $$$j$$$ без остатка. Чтобы найти произведения всех подмножеств множества из $$$k$$$ элементов рассмотрим два случая:

• произведение $$$a_i \cdot a_i$$$ будет учитываться $$$2^{k-2} \cdot (k - 1)$$$ раз. Каждый элемент во множестве $$$A$$$ может быть удален и это добавит произведение $$$a_i^2$$$. Количество элементов $$$k - 1$$$ и количество выбрать остально подмножество $$$2^{k-2}$$$;

• произведение $$$a_i \cdot a_j$$$ будет учитываться $$$2^{k-3} \cdot (k - 2) + 2^{k-2}$$$. Первое слагаемое по аналогии с примером выше. А второе получается, если из множестве $$$A$$$ удалять $$$a_i$$$~-- количество способов выбрать подмножество из $$$k - 2$$$ элементов это $$$2^{k-2}$$$.

Осталось только считать отдельные суммы $$$a_i \cdot a_i$$$ и $$$a_i \cdot a_j$$$ для всех элементов, которые делятся на $$$i$$$. Для этого можно поддерживать для уже добавленных чисел их количество, сумму, сумму квадратов чисел и попарную сумму чисел. Ответ на задачу будет $$$ans_1$$$.

Для начала предположим, что все протестующие находятся в корне дерева. Тогда ответом на задачу будет $$$\lceil \frac{a_1}{leafs} \rceil$$$, где $$$leafs$$$ -- количество листов в дереве. По принципу Дирихле это будет минимальное возможное количество задержанных.

Ответом на исходную задачу будет $$$max_i{\lceil \frac{sum(a_v)}{leafs_i} \rceil}$$$, где $$$v$$$ лежит в поддереве $$$i$$$, $$$leafs_i$$$ -- количество листьев в поддереве $$$i$$$.

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

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

Давайте будет перебирать ответ. Пусть текущий ответ это $$$x$$$, тогда мы можем получить его только тогда, когда не существует подмассивов, у которой MEX равен $$$x$$$. Заметим, что нам нужно проверить MEX подмассивов, которые находятся между всеми вхождениями числа $$$x$$$. Делать это можно, например, с помощью дерева отрезков, обрабатывая его вхождения по порядку. Число, для которого MEX не найдётся и будет ответом.

Можно заметить, что для получения максимальной разницы суммировать числа можно только двумя способами -- оставить изначальным массива как есть или объединить все числа, которые больше чем $$$m/2$$$ в одну сумму. Если на каком-либо префиксе нам лучшим (с большей разницей) стал второй вариант, то и для всех последюущих префиксов этот вариант будет лучше для фиксированного $$$m$$$. Еще можно заметить, что если для $$$m_i$$$ второй вариант стал лучше, то для $$$m_j$$$ такое, что $$$m_j \le m_i$$$, второй вариант тоже будет лучше. Таким образом отсортировав все $$$m_i$$$ можно находит префиксы для каждого запроса в которых первый вариант переходит во второй. Останется только просуммировать правильно нужные нам значения первого варианта для префиксов до определенно длины и второго варианта для префиксов начиная с определенной длины. Для этого нужно уметь находить количество элементов, сумму индексов, сумму элементов и сумму индекс умноженное на элемент на префиксах и суффиксах массива с нижним или верхним ограничением на элементы. Это можно сделать с помощью дерева отрезков или дерева Фенвика используя в качество индексов значения элементов и поддерживая состояние на текущий момент (для текущего префикса и текущего суффикса). В авторском решении для получения состояния на суффиксе использовалось персистентное дерево отрезков.

Четырехугольник можно построить когда $$$max(a, b, c, d) < a + b + c + d - max(a, b, c, d)$$$, то есть сумму минимальных трех чисел больше максимального. Для этого в качестве $$$d$$$ можно было выбрать $$$max(a, b, c)$$$ или $$$a + b + c - 1$$$.

Заметим, что если значение $$$a_{1, 1}$$$ равняется некоторому числу $$$x$$$, то значения $$$a_{n, 1}$$$, $$$a_{1, m}$$$ и $$$a_{n, m}$$$ также должны быть равны $$$x$$$ по свойству палиндромов. Аналогичное свойство выполняется для всех следующих элементов $$$a_{x, y}$$$ ($$$a_{x, y}=a_{n - x + 1, y}=a_{1,m - y + 1}=a_{n - x + 1, m - y + 1}$$$), поэтому задача сводится к поиску числа, к которому выгодно свести текущую четверку чисел (для некоторых позиций в матрице это количество меньше четырех). Данное число является медианой этих чисел (средним в отсортированном множестве). Ответом будет сумма разниц медианы <<четверки>> с каждым числом в <<четверке>> по всем <<четверкам>>.

Пусть максимальное количество флагов первого типа, которое можно пошить равно $$$p$$$, а второго типа $$$q$$$. Общий цвет у обоих флагов красный. При этом первый флаг использует в два раз меньше красного, чем второй. Поэтому оптимальный вариант будет в зависимости от того, что больше $$$2 \cdot a$$$ или $$$b$$$. Оптимальный ответ будет одним из следующих:

• пошить $$$p$$$ флагов первого типа и флаги второго типа на остаток (возможен максимум при $$$2 \cdot a \ge b$$$);
• пошить $$$q$$$ флагов второго типа и флаги первого типа на остаток (при $$$2 \cdot a \le b$$$);
• пошить $$$p-1$$$ флагов первого типа и флаги второго типа на остаток (при $$$2 \cdot a \ge b$$$, но $$$a < b$$$).

Проверим этих три варианта и найдем максимальный ответ.

Допустим существует какой-то ответ $$$a + b = c$$$ из заданных цифр. Давайте посмотрим на младший разряд в $$$a$$$ и $$$b$$$. Если в этом разряде нет переноса единицы, то мы можем использовать только младший разряд в ответе (то есть $$$c \le 9$$$). Если есть перенос, то давайте смотреть следующий разряды, пока есть перенос единицы дальше. Когда найдем разряд, в котором нет переноса, то мы можем оставить только этот разряд и младший~-- сумма по-прежнему будет сходиться.

Из этого следует, что числа $$$a$$$ и $$$b$$$ будут меньше $$$100$$$. Мы переберем все возможные пары $$$a$$$ и $$$b$$$, посчитаем $$$c = a + b$$$ и посмотрим хватает ли заданных цифры, чтобы сложить числа.

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

Сразу заметим, что если $$$x > n$$$, то ответ 0, так как мы не можем набрать $$$x$$$ элементов, которые являются степенью двойки. Также заметим, что всего 30 различных степеней двоек, не превосходящих $$$10^9$$$.

Рассмотрим случай, когда $$$x$$$ является степенью двойки. Тогда очевидно, что числа, которые при делении на $$$x$$$ дают степень двойки, также являются степенью двойки. Тогда на каждую позицию мы обязаны поставить некоторую степень двойки, тогда итоговый ответ будет равняться $$$30^n$$$.

В противном случае, посчитаем количество чисел, которые при делении на $$$x$$$ дают степень двойки, пусть их $$$k$$$. Тогда переберём количество степеней двоек $$$i$$$ от $$$x$$$ до $$$n$$$, которые мы поставим. Количество способов выбрать $$$i$$$ позиций это $$$C(n, i)$$$, а количество способ поставить на эти $$$i$$$ позиций степени двойки, это $$$30^i$$$. Тогда итоговое количество способов расставить степени двойки — это $$$C(n, i) \cdot 30^i$$$. Тогда количество способов расставить оставшиеся числа — $$$k^{n-i}$$$. Проанализировав это, получаем итоговый ответ как $$$\sum_{i=x}^{n} C(n, i) \cdot 30^i \cdot k^{n-i}$$$.

Давайте считать для каждой цифры сколько раз она будет входить в конечную сумму и в каком разряде. Обозначим $$$m$$$ как длину числа $$$n$$$. Рассмотрим цифру $$$a_i$$$ на позиции $$$i$$$ в числе $$$n$$$ ($$$1 \le i \le m$$$). Если будет удалена какая-то часть числа слева от цифры, то текущая цифра останется в свое разряде~-- в ответ добавится количество способов удалить подотрезок слева умноженное на текущий разряд $$$i * (i - 1) / 2 \times 10^{m - i} \times a_i$$$. Если будет удален отрезок справа, то разряд будет меняться -- $$$(j + 1) \times 10^j \times a_i$$$ для всех $$$0 \le j < m - i$$$, или тоже самое ($$$\sum_{j=0}^{m - i - 1}{(j + 1) \times 10^j}) \times a_i$$$. Сумма по $$$j$$$ можно предпросчитать для всех значений.

Можно построить граф с вершинами в стартовой точке и всех точках быстрого перемещения. Расстояние между вершинами $$$(x_1,y_1)$$$ и $$$(x_2,y_2)$$$ вычисляется как $$$min(|x_1 - x_2|, |y_1 - y_2|)$$$. Чтобы не проводить все $$$m * (m + 1) / 2$$$ ребер в графе заметим, что для пары точек $$$(x_1,y_1)$$$ и $$$(x_2,y_2)$$$ таких, что $$$|x_1 - x_2| \le |y_1 - y_2|$$$, если существует точка с координатой $$$x_3$$$ такой, что она находится между $$$x_1$$$ и $$$x_2$$$ ($$$min(x_1, x_2) \le x_3 \le max(x_1, x_2)$$$), то расстояние между первой и второй точкой будет равно сумме расстояний между первой и третьей и между третьей и второй. В таком случае ребро между первой и второй точкой проводить не нужно~-- оно будет излишним. Получается для каждой точки графа достаточно будет провести ребра в ближайшие по оси $$$x$$$ точки в обе стороны. Аналогично по $$$y$$$. Далее в построенном графе найдем минимальное расстояние от стартовой точки до каждой точки графа $$$(x, y)$$$ и просуммируем с расстоянием до конечной точки $$$(f_x, f_y)$$$, которое равно $$$|x - f_x| + |y - f_y|$$$. Среди всем расстояний найдем минимальное.

Давайте находить ответ $$$ans_i$$$ для всех суффиксов, начиная с наименьшего по длине. $$$ans_n$$$ равен пустой строке. Тогда если $$$s_i = s_{i + 1}$$$ ($$$0 \le i + 1 < n$$$), то $$$ans_i = min(s_i + ans_{i + 1}, ans_{i + 2})$$$, а иначе $$$ans_i = s_i + ans_{i + 1}$$$. Чтобы быстро находить минимум из двух строк их можно хранить <<двоичными подъемами>>~-- $$$next_{i,j}$$$ будет равен позиции в строке $$$s$$$, на которой будет находиться $$$2^j$$$ символ $$$ans_i$$$, а $$$hash_{i,j}$$$~-- хеш от префикса $$$ans_i$$$ длины $$$2^j$$$. Значения для $$$(i,j)$$$ можно получить из $$$(i,j-1)$$$ и $$$(i + 2^{j-1},j-1)$$$. Для восстановления ответа нам будет достаточно $$$next_{i,j}$$$ и для простоты можно дополнительно хранить длину каждого ответа.

Для того, чтобы найти НОК чисел на отрезке можно для каждого простого числа найти максимальную степень с какой он входит в какое-либо число на отрезке и с этой степенью домножить его в ответа. Давайте считать НОК для простых чисел меньших $$$\sqrt{MaxA}$$$ и не меньших $$$\sqrt{MaxA}$$$ отдельно при помощи дерева отрезков.

Простых чисел меньших $$$\sqrt{MaxA}$$$ $$$k=86$$$. Давайте в каждом подотрезке дерева хранить отсортированный список простых чисел с их максимальной степенью. Объединение двух отрезков можно сделать за $$$O(k)$$$. Тогда построение всего дерева можно сделать за $$$O(n \cdot k)$$$. Для того, чтобы ответить на запрос, разобьем его на $$$O(log(n))$$$ подотрезков дерева отрезков и последовательно объединим их за $$$O(k)$$$.

Для каждого числа $$$a_i$$$ массива будет не больше одного просто делителя $$$p_i$$$, большего $$$\sqrt{MaxA}$$$. Для запроса нужно найти произведение уникальных чисел $$$p_i$$$ на отрезке. Для этого для каждого такого простого $$$p_i$$$ числа найдем $$$prev_i$$$ ближайшую позицию слева в массиве такого же простого числа (или $$$-1$$$ если слева такого простого нет). Для подотрезка будем хранить отсортированный список пар $$$(prev_i, p_i)$$$, а также предпросчитаем произведение $$$p_i$$$ для каждого префикса. Теперь для каждого подотрезка дерева отрезков, который будет входить в запрос $$$(l,r)$$$, нужно выбрать все такие пары, для которых $$$prev_i < l$$$ и перемножить $$$p_i$$$. Так как список упорядоченный, то все эти числа будут образовывать префиксе. Префикс можно найти с помощью двоичного поиска за $$$log(n)$$$ и использовать предпросчитанное произведение.

Итоговая сложность $$$O(n \cdot k + q \cdot log(n) \cdot k + q \cdot log^2(n))$$$, где $$$k=\frac{\sqrt{MaxA}}{ln(\sqrt{MaxA})}$$$ (количество простых чисел до корня).