$$$\qquad$$$На галактическом экзамене нужно сдать таблицу умножения. Но если в 2022 каждый школьник должен был знать обычную таблицу умножения. То в далёком будущем каждый должен знать не только произведения двух любых натуральных чисел, но и количество различных чисел которые являются произведением двух любых натуральных чисел в таблице.

Даны два массива чисел $$$a$$$ и $$$b$$$ длины $$$n$$$.

Назовём крутостью двух массивов значение, равное $$$\sum_{i = 1}^n GCD(a_i, b_i)$$$.

Вам разрешается переставлять числа как угодно только в массиве $$$b$$$. Необходимо найти максимальную крутость.

Дана функция

$$$$$$ f(x)=\begin{cases} x - b + 1, & x \gt a \\ f(f(x + b)), & x \leq a \\ \end{cases} $$$$$$

и $$$t$$$ запросов. Каждый запрос содержит коэффициенты $$$a$$$, $$$b$$$ и аргумент $$$x$$$. Требуется найти $$$f(x)$$$

Пете в руки попался необычный калькулятор. В нем нет привычных кнопок «+», «-», «*» и «/». Может быть это и к лучшему, ведь кнопки для набора цифр («0», «1», ..., «9») и получения результата («=») расположены на своих местах. Но что самое необычное в этом калькуляторе, так это наличие кнопок «^{}» и «^{}^{}».

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

Кнопка «^{}» означает операцию возведения в степень $$$a^b$$$. Например, если ввести в калькуляторе выражение «2^{}3», то в результате, он выведет число $$$2^3 = 8$$$.

Кнопка «^{}^{}» означает выполнение тетрации $$$\displaystyle {^{b}a}=\underbrace {a^{a^{\cdot ^{\cdot ^{\cdot ^{a}}}}}} _{b}$$$. Например, если ввести выражение «2^{}^{}3», то в результате калькулятор выведет число $$$^{3}2 = 2^{2^2} = 16$$$.

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

Помогите Пете вычислить значения оставшихся выражений. Для этого необходимо реализовать программу, обрабатывающую выражение с учетом приоритета операций. Тетрация имеет более высокий приоритет (по сравнению с операцией возведения в степень), поэтому такие операции должны быть выполнены в первую очередь. Также нужно учитывать, что вычисление степеней и тетраций необходимо начинать с самых дальних уровней к начальному. Например запись «a^{}^{}b^{}^{}c» должна быть вычислена как $$$^{(^{c}b)}a$$$, а выражение «a^{}b^{}c» — как $$$a^{(b^c)}$$$.

$$$\qquad$$$Старший Координатор Библброкс очень любит играть в Космическое Го и, между прочим, очень не любит проигрывать. По правилам Космического Го, игральным полем является прямоугольный гобан, расчерченный вертикальными и горизонтальными линиями. Стандартный космический гобан состоит из $$$N$$$ x $$$N$$$ ячеек в декартовой системе координат $$$(x, y)$$$, где $$$(1 \leq x, y \leq N)$$$.

$$$\qquad$$$В каждой ячейке может находиться один из трех объектов: заблокированная ячейка, игровая ячейка или Го-иси. Окрашены они в красный, зеленый и белый цвета соответственно. Для каждого $$$i$$$, $$$(1 \leq i \leq N)$$$, в $$$i$$$-той колонке, ячейки с самого нижнего ряда до $$$A_i$$$-того ряда снизу — красные ячейки, которые обозначают заблокированные поля.

$$$\qquad$$$Существует $$$M$$$ белых ячеек, которые обозначают Го-иси. У каждого Го-иси есть своя целочисленная положительная цена удаления с игрового поля. Каждая $$$j$$$-тая белая ячейка $$$(1 \leq j \leq M)$$$ является ячейкой $$$(X_j, Y_j)$$$. Все остальные ячейки являются зелеными и обозначают свободные ячейки.

Некоторый прямоугольный участок поля считается защищенным если на нём:

$$$\qquad$$$1. Отсутствуют красные ячейки.

$$$\qquad$$$2. Находится 2 и более белых Го-иси.

$$$\qquad$$$Чтобы победить, Библброксу необходимо удалить все защищенные участки (одно удаление является одним ходом). Библброкс хочет всегда ставить рекорды, а чтобы получить наилучший результат, ему необходимо добиться минимальной стоимости всех ходов. Библброксу тяжело вычислять защищенные участки, и он просит нас написать программу, которая поможет ему выявлять и разрушать защищенные участки.

$$$\qquad$$$Вы конечно же вызвались помочь Библброксу в решении столь интересной задачи.

$$$\qquad$$$Во Вселенной Адамса существует $$$N$$$ планет, пронумерованных от $$$1$$$ до $$$N$$$. Планеты соединены космическими лифтами в количестве $$$N-1$$$. $$$i$$$-тый космический лифт $$$(1 \leq i \leq N-1)$$$ соединяет планету $$$A_i$$$ с планетой $$$B_i$$$. На каждом космическом лифте можно двигаться в любом направлении. Вы можете попасть с любой планеты на любую другую планету используя космические лифты.

$$$\qquad$$$В настоящее время Вселенная Адамса разделена на $$$K$$$ галактик, пронумерованных от $$$1$$$ до $$$K$$$. Планета $$$j$$$ $$$(1 \leq j \leq N)$$$ относится к галактике $$$C_j$$$. К каждой галактике относится минимум одна планета.

$$$\qquad$$$Одна из галактик будет выбрана Старшим Координатором Библброкосом в качестве главного транспортного узла (ГТУ). По причинам государственной безопасности, ГТУ должен соответствовать следующим условиям.

$$$\qquad$$$Должно быть возможно попасть с любой планеты ГТУ на любую другую планету ГТУ проходя только планеты, которые относятся к ГТУ.

$$$\qquad$$$Тем не менее, Старший Координатор Библброкс заметил, что может существовать случай, когда ни одна из галактик Вселенной Адамса не удовлетворяет данному условию, и он не сможет выбрать ГТУ.

$$$\qquad$$$Для того, чтобы решить данную проблему, Старший Координатор Библброкс может объединять галактики. А именно может выполнять следующую операцию.

$$$\qquad$$$Выбрать $$$x$$$ и $$$y$$$ удовлетворяющие условию $$$(1 \leq x, y \leq K)$$$ и $$$x \neq y$$$ и менять планеты галактик так, что планеты галактики $$$y$$$ станут планетами галактики $$$x$$$.

$$$\qquad$$$Так как объединение галактик — это крайне трудозатратно, Старший Координатор Библброкс хочет минимизировать количество объединений, для выбора ГТУ.

$$$\qquad$$$Так как Библброкс координирует всю Вселенную Адамса, что является крайне непростой задачей, он не сможет справиться с этим самостоятельно и поэтому обратился к вам за помощью. Вычислите минимальное количество объединений галактик для выбора ГТУ.

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

Торговец сказал Вадиму, что сможет покупать у него каждую доску за $$$m * S$$$, где $$$S$$$ - площадь доски. Изначально она представляет собой прямоугольник, три из сторон которого - ровные, а четвёртая обломана. Мальчик расположил доску на координатной плоскости отломанной стороной вверх так, чтобы её нижняя сторона совпала с осью абсцисс. Тогда щепки на чертеже Вадим может описать как ломаную, состоящую из $$$n$$$ вершин (Рис.1).

Затем он узнал в строительном магазине, что одна капля смолы стоит $$$k$$$ монет. Там же ему подсказали, что на его чертеже одна капля смолы займёт ровно единицу площади и, чтобы помочь, пообещали продать даже нецелое количество капель смолы. После того, как Вадим зальёт смолу и она застынет (Рис. 2), он спилит все оставшиеся щепки и продаст досточку (на рис. 3 Вы можете увидеть линию, по которой Вадим будет резать). Помогите Вадиму: напишите программу, которая по описанию досточки и ценам $$$m$$$ и $$$k$$$ сможет посчитать максимальное количество денег, которое сможет получить Вадим с этой досточки.

Гарантируется, что ответ помещается в double. Ответ следует выводить с точностью до $$$10^{-6}$$$

Егор проходит отбор в студсовет ФКСиС. В студсовете состоит $$$n - 1$$$ человек. Егор условно пронумеровал их от $$$2$$$ до $$$n$$$. Председатель студсовета имеет номер $$$n$$$. Чтобы попасть в студсовет, Егор должен набрать как можно больше баллов. $$$i$$$-й студсоветчик начисляет Егору $$$a_i$$$ баллов за выполненное задание. А также некоторые из студсоветчиков могут направить Егора к коллегам, чтобы он продолжил выполнять задание у кого-нибудь из них. Так, если студсоветчик с номером $$$k$$$ может направить Егора к коллегам, он называет ему два числа: $$$l_k$$$ и $$$r_k$$$. Это означает, что Егор может выбрать любого студсоветчика с номером $$$q \in [l_k, r_k]$$$ и пойти к нему. Без направления Егор идти не может.

Себя Егор обозначил номером $$$1$$$.

Помогите Егору просчитать свои шансы. Посчитайте максимальное количество баллов, которое Егор может набрать. Если Егор не сможет добраться до председателя студсовета, выведите «No»(Без кавычек).

Дан массив длины $$$n$$$, состоящий только из чисел $$$1, 2, 3, 4, 5, 6$$$.

Вам дано $$$q$$$ запросов вида $$$t$$$, $$$l$$$, $$$r$$$ ($$$l \leq r$$$), где $$$t$$$ - тип запроса (1 или 2), а $$$l$$$ и $$$r$$$ - соответственно левая и правая границы подотрезка:

- $$$t = 1$$$. Отсортируйте подотрезок $$$[l, r]$$$ в порядке неубывания. Данный тип запросов не требует ответа.

- $$$t = 2$$$ Выведите длину наибольшей возрастающей подпоследовательности на отрезке $$$[l, r]$$$

Вова получил от преподавателя домашнее задание. На его электронную почту от преподавателя пришло письмо, содержащее число $$$n$$$ и строку длиной $$$9 * n$$$ символов, состоящую из заглавных латинских букв. Так как преподаватель очень любит родной чемпионат по программированию, он хочет найти минимальное количество букв, которые нужно заменить в отправленной строке так, чтобы подстрока «BSUIROPEN» (без кавычек) встречалась в строке максимально возможное количество раз. Помогите Вове решить эту задачу.