Недавно Васе попалась такая задача, в которой были заданы три натуральных числа A, B и C из диапазона [1, N], и требовалось проверить, верно ли равенство AB = C. Недавно Вася изучил понятие цифрового корня из числа. Напомним, что цифровой корень d(x) числа x равен сумме цифр s(x) этого числа, если s(x) ≤ 9, и равен d(s(x)) в противном случае. К примеру, цифровой корень числа 6543 вычисляется следующим образом: d(6543) = d(6 + 5 + 4 + 3) = d(18) = 9. Вася вычитал, что цифровой корень произведения чисел равен цифровому корню произведения цифровых корней сомножителей, т.е. d(xy) = d(d(x)d(y)). И ему пришел в голову такой способ решения задачи: посчитать цифровые корни и проверить выполнение этого условия. Однако Вася подозревает, что это условие не является достаточным. Поэтому он просит вас посчитать, сколько существует тестовых примеров для встреченной им задачи таких, что предложенный им алгоритм ошибется.

Вам дан прямоугольный параллелепипед с целыми положительными сторонами \(A\), \(B\) и \(C\).

Найдите количество различных троек целых чисел (\(a\), \(b\), \(c\)) таких, что \(1\leq a\leq b\leq c\) и параллелепипед \(A\times B\times C\) можно замостить параллелепипедами \(a\times b\times c\). Обратите внимание, что все замощающие параллелепипеды должны быть ориентированы в одну сторону.

Например, параллелепипед \(1\times 5\times 6\) можно разделить на параллелепипеды \(1\times 3\times 5\), но нельзя – на параллелепипеды \(1\times 2\times 3\).

Близится следующий сезон, поэтому Вы решили собрать команду из двух или трех человек. У Вас есть \(n\) кандидатов, \(i\)-й кандидат имеет ранг \(a_i\). Но у Вас есть какие-то странные ограничения: если Ваш ранг \(v\) и Вы выбрали кандидатов \(i\) и \(j\), то должно выполняться условие \(GCD(v, a_i) = X\) и \(LCM(v, a_j) = Y\).

Вы очень опытный участник, поэтому Вы можете сделать свой ранг любым неотрицательным целым числом, однако \(X\) и \(Y\) связаны с Вашим днем рождения, поэтому они фиксированы.

И вот Вы хотите узнать количество пар \((i, j)\) таких, что существует \(v\), что \(GCD(v, a_i) = X\) и \(LCM(v, a_j) = Y\). Разрешена ситуация \(i = j\), просто ваша команда будет состоять из двух участников.

\(GCD\) — это наибольший общий делитель двух чисел, а \(LCM\) — наименьшее общее кратное.

Хомяк Дима обожает грызть различные объекты, среди которых клетки, коробки, авторы плохих задач и даже деревья!

Недавно он обнаружил двоичное дерево поиска и тут же сгрыз все его ребра, в результате чего вершины дерева перемешались в случайном порядке. Дима знает, что если Андрей, который кропотливо строил дерево на протяжении долгого времени, придет и увидит, что все разрушено, то он очень расстроится. По счастью, прежде чем сгрызть все ребра, Дима заметил, что для любых двух вершин, соединенных ребром, наибольший общий делитель их значений превосходит \(1\).

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

Дана бесконечная доска, состоящая из квадратных клеток. Изначально все клетки белого цвета.

У Вовы есть красный маркер и синий маркер. Красным маркером можно закрасить \(a\) клеток. Синим маркером можно закрасить \(b\) клеток. Если какая-то клетка не белая, то нельзя использовать маркер какого-либо цвета на ней. Каждый маркер должен был использован полностью, поэтому в конце на доске должно оказаться ровно \(a\) красных клеток и ровно \(b\) синих клеток.

Вова хочет раскрасить такой набор клеток, чтобы:

• они образовали прямоугольник, состоящий ровно из \(a+b\) закрашенных клеток;
• все клетки хотя бы одного цвета также образовали прямоугольник.

Некоторые примеры корректных раскрасок:

Некоторые примеры некорректных раскрасок:

Среди всех корректных раскрасок Вова хочет выбрать такую, что ее периметр минимален. Какой минимальный периметр Вова может получить?

Гарантируется, что существует хотя бы одна корректная раскраска.

Вам задан генератор кортежей чисел \(f^{(k)} = (f_1^{(k)}, f_2^{(k)}, \dots, f_n^{(k)})\), где \(f_i^{(k)} = (a_i \cdot f_i^{(k - 1)} + b_i) \bmod p_i\) и \(f^{(0)} = (x_1, x_2, \dots, x_n)\). Здесь \(x \bmod y\) означает остаток от деления \(x\) на \(y\). Все \(p_i\) — простые числа.

Можно заметить, что при фиксированных наборах \(x_i\), \(y_i\), \(a_i\) начиная с некоторого номера кортежи \(f^{(k)}\) будут повторять кортежи с меньшими номерами. Найдите максимальное количество различных кортежей (из всех \(f^{(k)}\) при \(k \ge 0\)), которые может выдать данный генератор, если \(x_i\), \(a_i\), \(b_i\) — целые числа в диапазоне \([0, p_i - 1]\) и могут быть выбраны произвольно. Так как ответ может быть слишком большим, выведите остаток от его деления на \(10^9 + 7\).

У вас есть \(n\) целых чисел \(a_1, a_2, \ldots, a_n\). Каждое из \(a_i\) имеет от \(3\) до \(5\) делителей. Пусть \(a = \prod a_i\) — произведение всех входных чисел. Найдите количество делителей \(a\). Поскольку это число может быть очень большим, выведите его остаток от деления на простое число \(998244353\).

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

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

В королевстве Осени \(n\) городов, пронумерованных от \(1\) до \(n\). От любого города можно добраться до любого другого, используя некоторые из \(n-1\) дорог в королевстве.

В этом году правительство приняло решение разбить королевство на регионы. После разбиения будут существовать регионы нескольких уровней, при этом само королевство будет являться регионом первого уровня. Любой регион уровня \(i\) должен быть разделен на несколько (хотя бы два) регионов уровня \(i+1\), если это не регион последнего уровня. Каждый город должен принадлежать ровно одному региону каждого уровня. Внутри одного региона, между любыми двумя городами в нем должен существовать путь, проходящий только по городам этого региона.

Согласно исследованию, для каждого города \(i\) есть уровень важности — \(a_i\). Все регионы одного уровня должны иметь одинаковую сумму этих значений.

Ваша задача состоит в том, чтобы узнать, сколько существует планов разбиения королевства на регионы, чтобы все условия выполнялись. Два плана считаются различными тогда и только тогда, когда количество уровней в них различно, или существует пара городов, которые для какого-то уровня находятся в одном регионе в одном плане, но в разных регионах того же уровня в другом. Поскольку ответ может быть очень большим, выведите его по модулю \(10^9+7\).

Рассмотрим некоторое положительное целое число \(x\). Его разложение на простые имеет вид \(x = 2^{k_1} \cdot 3^{k_2} \cdot 5^{k_3} \cdot \dots\)

Назовем число \(x\) изящным, если наибольший общий делитель последовательности \(k_1, k_2, \dots\) равен \(1\). Например, числа \(5 = 5^1\), \(12 = 2^2 \cdot 3\), \(72 = 2^3 \cdot 3^2\) изящные, а числа \(8 = 2^3\) (\(GCD = 3\)), \(2500 = 2^2 \cdot 5^4\) (\(GCD = 2\)) — нет.

Посчитайте количество изящных чисел от \(2\) до \(n\).

В каждом тесте содержится несколько значений \(n\), для каждого из них необходимо решить задачу независимо.

Все думают, что марсиане зеленые, но на самом деле они розоватые с металлическим отливом и полные. У Ажса есть два мешочка с различными неотрицательными числами. Числа в мешочках не пересекаются, а объединение множеств чисел равно \(\{0,1,…,M-1\}\) для некоторого положительного числа \(M\).

Ажс достает одно число из первого мешочка, одно число из второго, и вычисляет их сумму по модулю \(M\).

Какие остатки по модулю \(M\) Ажс не может получить после такого действия?

Вам даны два массива \(a_0, a_1, \ldots, a_{n - 1}\) и \(b_0, b_1, \ldots, b_{m-1}\), и целое число \(c\).

Вычислите следующую сумму:

\(\)\sum_{i=0}^{n-1} \sum_{j=0}^{m-1} a_i b_j c^{i^2\,j^3}\(\)

Так как это число может быть ну очень большим, выведите его по модулю \(490019\).

Аркадий и его друзья любят играть в шашки на доске \(n \times n\). Строки и столбцы доски пронумерованы от \(1\) до \(n\).

Друзья недавно выиграли какой-то турнир, поэтому Аркадий хочет поздравить их и подарить конфеты. Вспомнив старинную притчу (но не ее мораль), Аркадий решил дать друзьям по одному набору конфет за каждую клетку доски: набор конфет, соответствующий клетке \((i, j)\), будет состоять из ровно \((i^2 + j^2)\) конфет особенного для этой клетки типа.

Всего друзей, выигравших турнир, \(m\). Сколько же из этих \(n \times n\) наборов конфет можно разделить поровну на \(m\) частей, не разделяя конфеты на части? Обратите внимание, что каждый набор нужно делить независимо, так как конфеты в разных наборах разные.

Учитель JATC по математике всегда даёт их классу разные интересные математические задачки, чтобы им не было скучно. Сегодня задачка выглядит следующим образом. Дано целое число \(n\), вы можете выполнить следующие операции ноль или более раз:

• mul \(x\): умножает \(n\) на \(x\) (где \(x\) является произвольным положительным целым числом).
• sqrt: заменяет \(n\) на \(\sqrt{n}\) (эту операцию можно выполнить только если \(\sqrt{n}\) является целым числом).

Вы можете выполнять данные операций столько раз, сколько вы хотите. Какого минимального значения \(n\) можно добиться и какое минимальное количество операций нужно сделать, чтобы получить это минимальное значение?

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

You are given two positive integers \(d\) and \(s\). Find minimal positive integer \(n\) which is divisible by \(d\) and has sum of digits equal to \(s\).

Chouti работает над странной математической задачей.

Была некоторая последовательность из \(n\) положительных целых чисел \(x_1, x_2, \ldots, x_n\), где число \(n\) чётное. Последовательность была очень особенной, а именно для каждого целого \(t\) от \(1\) до \(n\), \(x_1+x_2+...+x_t\) является квадратом некоторого целого числа (то есть полным квадратом).

Неведомым образом, числа с нечётными индексами пропали, то есть известны только числа с чётными индексами, другими словами \(x_2, x_4, x_6, \ldots, x_n\). Задача состоит в том, чтобы восстановить изначальную последовательность. Он снова просит у вас помощи с решением этой задачи.

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

Факторизовать числа сложно. RSA Factoring Challenge предлагает \($100\,000\) тому, кто сможет факторизовать RSA-\(1024\), \(1024\)-битное произведение двух простых чисел. До этого времени никому не удалось получить приз. Мы хотим факторизовать \(1024\)-битное число.

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

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

• + x y, где \(x\) и \(y\) — целые числа между \(0\) и \(n-1\). Возвращает \((x+y) \bmod n\).
• - x y, где \(x\) и \(y\) — целые числа между \(0\) и \(n-1\). Возвращает \((x-y) \bmod n\).
• * x y, где \(x\) и \(y\) — целые числа между \(0\) и \(n-1\). Возвращает \((x \cdot y) \bmod n\).
• / x y, где \(x\) и \(y\) — целые числа между \(0\) и \(n-1\), а \(y\) взаимно простое с \(n\). Возвращает \((x \cdot y^{-1}) \bmod n\), где \(y^{-1}\) — обратное к \(y\) число по модулю \(n\). Если \(y\) не взаимно простое с \(n\), тогда будет возвращено \(-1\).
• sqrt x, где \(x\) — число между \(0\) и \(n-1\), и оно взаимно просто с \(n\). Возвращает \(y\) такое, что \(y^2 \bmod n = x\). Если есть несколько таких целых чисел, то только одно из них будет возвращено. Если таких чисел нет, то будет возвращено \(-1\).
• ^ x y, где \(x\) и \(y\) — целые числа между \(0\) и \(n-1\). Возвращает \({x^y \bmod n}\).

Найдите факторизацию \(n\), которое является произведением от \(2\) до \(10\) различных простых чисел типа \(4x + 3\), где \(x\) — целое.

Из-за технических сложностей мы вынуждены ограничить количество запросов до \(100\).

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

Количество запросов не ограничено. Однако ваша программа должна (как всегда) завершиться за определенное время. Время работы интерактора также засчитывается в ограничение по времени. Максимальное время выполнения каждого запроса приведено ниже.

• + x y — до \(1\) мс.
• - x y — до \(1\) мс.
• * x y — до \(1\) мс.
• / x y — до \(350\) мс.
• sqrt x — до \(80\) мс.
• ^ x y — до \(350\) мс.

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

Алексей решил попытать счастья в телешоу. Однажды он сходил на викторину. После того, как он идеально ответил на вопросы «Как обычно называют псевдоним в интернете?» («Ум... может быть ник?»), «В честь какого известного изобретателя назвали единицу силы магнитного поля?» («Ум... Никола Тесла?»), он решил посетить гораздо более сложное телешоу: «Что в этом мультимножестве?!».

Это телешоу устроено следующим образом: есть \(n\) мультимножеств, пронумерованных от \(1\) до \(n\). Каждое из них изначально пусто. Затем, происходят \(q\) запросов, где каждый запрос имеет один из четырёх следующих типов:

• 1 x v — присвоить \(x\)-му мультимножеству мультимножество из одного элемента \(\{v\}\).
• 2 x y z — присвоить \(x\)-му мультимножеству объединение мультимножеств \(y\) и \(z\). For example: \(\{1, 3\}\cup\{1, 4, 4\}=\{1, 1, 3, 4, 4\}\).
• 3 x y z — присвоить \(x\)-му мультимножеству произведение \(y\)-го и \(z\)-го мультимножества. Произведение \(A \times B\) мультимножеств \(A\) и \(B\) определяется как \(\{ \gcd(a, b)\, \mid\, a \in A,\, b \in B \}\), где \(\gcd(p, q)\) обозначает наибольший общий делитель \(p\) и \(q\). Например, \(\{2, 2, 3\} \times \{1, 4, 6\}=\{1, 2, 2, 1, 2, 2, 1, 1, 3\}\).
• 4 x v — вас спрашивают, сколько раз число \(v\) встречается в мультимножестве \(x\). Так как викторина показал себя достаточно сложной в прошлом, то теперь нужно лишь сказать ответ на этот вопрос по модулю \(2\).

Обратите внимание, что \(x\), \(y\), и \(z\) в описании выше не обязательно различны. Для запросов \(2\)-го и \(3\)-го типа нужно сначала вычислить соответствующую сумму или произведение и лишь затем выполнить присвоение.

Алексея смущают запутанные правила шоу. Помогите ему узнать ответы на все запросы \(4\)-го типа.

Дано дерево из \(n\) вершин. На каждой вершине дерева записано число; на \(i\)-й вершине записано число \(a_i\).

Определим функцию \(g(x, y)\) как наибольший общий делитель всех чисел, записанных на вершинах на простом пути от вершины \(x\) до вершины \(y\) (включая эти две вершины). Также определим \(dist(x, y)\) как количество вершин на простом пути между \(x\) и \(y\), включая концы пути. \(dist(x, x) = 1\) для каждой вершины \(x\).

Посчитайте максимальное значение \(dist(x, y)\) по всем таким парам вершин, что \(g(x, y) > 1\).

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

Пусть \(f_1, f_2, \ldots, f_i, \ldots\) — бесконечная последовательность положительных целых чисел. Боб знает, что, если \(i > k\), то \(f_i\) может быть получена, используя следующую рекуррентную формулу:

\(\)f_i = \left(f_{i - 1} ^ {b_1} \cdot f_{i - 2} ^ {b_2} \cdot \cdots \cdot f_{i - k} ^ {b_k}\right) \bmod p,\(\)

или, если коротко,

\(\)f_i = \left(\prod_{j = 1}^{k} f_{i - j}^{b_j}\right) \bmod p,\(\)

где \(p = 998\,244\,353\) (известное простое), \(b_1, b_2, \ldots, b_k\) — известные целочисленные константы, а \(x \bmod y\) обозначает остаток от деления \(x\) на \(y\).

Боб потерял значения \(f_1, f_2, \ldots, f_k\), что очень печально: ведь они составляют основу последовательности! К счастью, Боб запомнил первые \(k - 1\) элементов последовательности: \(f_1 = f_2 = \ldots = f_{k - 1} = 1\), а также ее \(n\)-й элемент: \(f_n = m\). Найдите любое возможное значение \(f_k\). Если решений нет, скажите Бобу, что восстановить его любимую последовательность нельзя.

Вам дана двоичная матрица \(A\) размера \(n \times n\). Обозначим \(x\)-сжатие данной матрицы как матрицу \(B\) размера \(\frac{n}{x} \times \frac{n}{x}\), такую, что для всех \(i \in [1, n], j \in [1, n]\) выполняется условие \(A[i][j] = B[\lceil \frac{i}{x} \rceil][\lceil \frac{j}{x} \rceil]\).

Очевидно, \(x\)-сжатие возможно только в том случае, если \(x\) является делителем \(n\), но этого недостаточно. К примеру, у этой матрицы \(2 \times 2\) нет \(2\)-сжатия:

Для заданной матрицы \(A\) найдите максимальное \(x\), для которого возможно \(x\)-сжатие этой матрицы.

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

Егор очень любит математику, и недавно он получил высшую степень признания в математических кругах — Егор стал красным математиком. По такому поводу Саша решил поздравить Егора и подарить ему математический тест. В тесте содержался массив \(a\) длины \(n\) из целых чисел и ровно \(q\) запросов. Запросы бывают трёх типов:

1. «1 l r x» — увеличить все числа на отрезке от \(l\) до \(r\) в \(x\) раз.
2. «2 p x» — уменьшить число в позиции \(p\) в \(x\) раз (делимость гарантирована).
3. «3 l r» — найти сумму на отрезке от \(l\) до \(r\).

Так как сумма может быть очень большой, то Саша попросил Егора вычислить лишь её остаток от деления на число \(mod\).

Так как Егор теперь красный математик, ему больше некогда решать столь простые задачи, поэтому, чтобы не обидеть Сашу, он попросил вас помочь ему и найти ответы на все запросы \(3\)-го типа.

Казалось бы, что общего может быть у наибольшего общего делителя и битовых операций? Самое время это выяснить.

Пусть вам дано целое положительное число \(a\). Вы хотите выбрать такое целое число \(b\) от \(1\) до \(a - 1\) включительно, чтобы наибольший общий делитель (НОД) чисел \(a \oplus b\) и \(a \> \& \> b\) был как можно больше. Иными словами, необходимо вычислить следующую функцию:

\(\)f(a) = \max_{0 < b < a}{gcd(a \oplus b, a \> \& \> b)}.\(\)

Здесь \(\oplus\) обозначает операцию побитового исключающего ИЛИ, а \(\&\) обозначает операцию побитового И.

Наибольший общий делитель двух целых чисел \(x\) и \(y\) — максимальное целое число \(g\) такое, что и \(x\), и \(y\) делится на \(g\) без остатка.

Вам дано \(q\) чисел \(a_1, a_2, \ldots, a_q\). Для каждого из этих чисел посчитайте наибольшее возможное значение наибольшего общего делителя (при оптимальном выборе \(b\)).

Аки любит числа. Особенно те, что заканчиваются на большое количество нулей. Например, число \(9200\) заканчивается на два нуля. Аки считает, что чем больше таких замыкающих нулей в записи числа, тем лучше.

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

Вам даны два целых числа \(n\) и \(b\) (записанные в десятичной системе счисления). Выясните, сколько замыкающих нулей в \(b\)-ичной (то есть в системе счисления с основанием \(b\)) записи числа \(n\,!\) (факториала \(n\)).

Вам дан массив \(a_1, a_2, \ldots, a_n\).

Необходимо выполнить \(q\) запросов следующих двух видов:

1. «MULTIPLY l r x» — для каждого \(i\) (\(l \le i \le r\)) нужно умножить \(a_i\) на \(x\).
2. «TOTIENT l r» — вычислить \(\varphi(\prod \limits_{i=l}^{r} a_i)\) по модулю \(10^9+7\), где \(\varphi\) обозначает функцию Эйлера.

Функцией Эйлера целого положительного числа \(n\) (обозначается как \(\varphi(n)\)) называется количество целых чисел \(x\) (\(1 \le x \le n\)), таких что \(\gcd(n,x) = 1\).

Совсем скоро наступит Международный женский день! Поликарп готовится к празднику.

В магазине продается \(n\) коробок с конфетами, в \(i\)-й коробке \(d_i\) конфет.

Поликарп хочет подготовить максимальное количество подарков для \(k\) подруг. Каждый подарок будет состоять из ровно двух коробок конфет. Чтобы \(k\) девушек могли поделить подарок поровну, сумма количеств конфет в подарке (в паре коробок) должна делится на \(k\). Иными словами, две коробки \(i\) и \(j\) (\(i \ne j\)) можно объединить в подарок, если \(d_i + d_j\) делится на \(k\).

Сколько максимум коробок сможет подарить Поликарп? Конечно, каждая коробка может быть в составе не более одного подарка. Поликарп не может использовать коробки «частично» или перераспределять конфеты между ними.

Это интерактивная задача.

Миша очень любит играть в кооперативные игры с неполной информацией. Сегодня он предложил десяти своим друзьям сыграть в кооперативную игру «Озеро».

Миша уже нарисовал игровое поле для предстоящей игры. Оно представляет из себя ориентированный граф, состоящий из двух частей. Одна из этих частей — дорожка вдоль берега озера, являющаяся циклом из \(c\) вершин. Вторая часть — тропинка от домика к озеру, представляющая из себя цепь из \(t\) вершин, причём из последней вершины этой цепи проведено ребро в одну из вершин дорожки вокруг озера — в ту, из которой на озеро открывается наилучший вид. Игровое поле Миша решил держать в секрете, так что никто кроме него не знает ни \(t\), ни \(c\).

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

В начале игры игровые фишки всех десяти игроков, для удобства пронумерованных цифрами от \(0\) до \(9\), располагаются в начале тропинки, в вершине у домика. Затем не более \(q\) раз Миша будет одновременно передвигать в следующие вершины фишки игроков, высказавших такое желание на этом ходу, а после этого объявлять, фишки каких игроков находятся в одной вершине, а каких — в разных.

Цель игры — перевести игровые фишки всех игроков в вершину с наилучшим видом на озеро, то есть в ту, которая отмечена финишным флагом. Мишины друзья не представляют, как можно выиграть в такой игре, не зная ни \(c\), ни \(t\), ни \(q\), но, к счастью для них, они ещё и ваши друзья. Помогите им: скоординируйте их действия так, чтобы победить.

Миша нарисовал такое игровое поле, что \(1 \le t, c\), \((t+c) \leq 1000\) и \(q = 3 \cdot (t+c)\).

Для того, чтобы отдать команды перемещения друзьям, выведите «next», а затем через пробел номера друзей, которым необходимо отдать команды. Например, чтобы отдать команду перемещения друзьям с номерами \(0\), \(2\), \(5\) и \(9\) выведите «next 0 2 5 9». На каждом ходу обязательно перемещать хотя бы одного из друзей.

В качестве ответа проверяющая программа выдаст сначала число \(k\), а потом \(10\) цифр, разбитых на \(k\) групп, разделённых пробелами. Друзья, соответствующие цифрам, находящимся в одной группе, находятся в одной вершине. Друзья, соответствующие цифрам, находящимся в разных группах, находятся в разных вершинах. Цифры в каждой группе следуют в порядке возрастания.

Например, ответ «2 05 12346789» означает, что друзья с номерами \(0\) и \(5\) находятся в одной вершине, а все остальные друзья в одной и той же, но другой вершине. Ответ «4 01 567 234 89» означает, что друзья Миши находятся в четырёх различных вершинах: в первой находятся друзья с номерами \(0\) и \(1\), во второй — друзья с номерами \(5\), \(6\) и \(7\), в третьей — друзья с номерами \(2\), \(3\) и \(4\), а в четвёртой — друзья с номерами \(8\) и \(9\).

После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• смотрите документацию для других языков.

Ответ «stop» вместо корректного означает, что ваша программа сделала некорректный запрос или превысила число запросов. Ваша программа должна немедленно завершиться после прочтения ответа «stop», вы получите вердикт Неправильный ответ. В противном случае вы можете получить любой вердикт, так как программа продолжит чтение из закрытого потока.

Взломы

Чтобы совершить взлом, выведите два целых числа \(t\) и \(c\) в одной строке (\(1 \le t, c\), \((t+c) \leq 1000\)).

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

Помогите Курту найти максимальное возможное произведение цифр среди всех целых чисел от \(1\) до \(n\).

Лягушка изначально находится в позиции \(0\) на числовой прямой. У лягушки есть два положительных числа \(a\) и \(b\). Из позиции \(k\) он может перейти либо в позицию \(k+a\), либо в \(k-b\).

Пусть \(f(x)\) — количество различных целых чисел, координаты которых лягушка может достичь, если она всегда будет находиться в интервале \([0, x]\). Лягушке не нужно посещать все эти числа за один раз, то есть число считается, если лягушка может каким-то образом достичь его, если она начинает с \(0\).

Дается число \(m\), найдите \(\sum_{i=0}^{m} f(i)\). Другими словами, найдите сумму по всем \(f(i)\) для всех \(i\) от \(0\) до \(m\).

Мы раздаем огромные красивые мешки, содержащие плитки с числами!

Мешок, который мы хотим вам подарить, содержит \(n\) плиток. На каждой из них записано одно число — \(1\) или \(2\).

Тем не менее, есть одно условие, которое вы должны выполнить, чтобы получить приз.

Вам нужно выложить все плитки из сумки в ряд в любом порядке, в котором вы пожелаете. Затем, мы посчитаем суммы на всех префиксах последовательности, а затем посчитаем, сколько из этих сумм являются простыми числами. Если вы хотите получить приз, вы должны максимизировать количество простых чисел, которые у вас получатся.

Сможете ли вы выиграть приз? Спешите, мешки ждут!

Задан массив \(a\), состоящий из \(n\) целых чисел \(a_1, a_2, \dots, a_n\).

Ваша задача — найти такую пару индексов \(i, j\) (\(1 \le i < j \le n\)), что \(lcm(a_i, a_j)\) минимально возможно.

\(lcm(x, y)\) — это наименьшее общее кратное \(x\) и \(y\) (минимально возможное положительное число такое, что и \(x\) и \(y\) являются делителями этого числа).

Мы загадали некоторые целое число \(x\). Вам задан список почти всех его делителей. Почти всех означает, что в списке есть все делители кроме \(1\) и \(x\).

Ваша задача — найти минимально возможное целое число \(x\), которое может быть загаданным числом, или сказать, что входные данные противоречивы и невозможно найти такое число.

Вам необходимо ответить на \(t\) независимых запросов.

Даша-путешественница решила использовать все заработанные за несколько лет отчисления на шоппинг. А где же еще лучше магазины, чем в Нлогонии?

Всего в Нлогонии \(n\) магазинов, пронумерованных от \(1\) до \(n\). В \(i\)-м из этих магазинов можно купить положительное целое число \(a_i\).

В каждый из последних \(m\) дней Даша покупала по одному числу в некоторых магазинах. В каждый из этих дней лисенок Жулик покупал по одному числу во всех магазинах, в которых Даша не купила число в этот день.

Дора считает, что Жулик соперничает с ней; она считает, что выиграла у Жулика в день \(i\), если и только если наименьшее общее кратное чисел, которые она купила в \(i\)-й день строго больше наименьшего общего кратного чисел, которые купил в \(i\)-й день Жулик.

Наименьшем общем кратном (НОК) набора целых чисел называется наименьшее положительное целое число, делящееся на все числа из набора.

К сожалению, Даша забыла, чему равны значения \(a_i\). Помогите Даше определить, существуют ли такие положительные целые числа \(a_i\), что она выигрывала у Жулика каждый день. Сами значения \(a_i\) находить не нужно.

Обратите внимание, возможно, что некоторые значения \(a_i\) в решении совпадают.

Вам дано целое число \(n\). Для каждого целого числа \(i\) от \(2\) до \(n\) найдите положительное целое число \(a_i\) такое, что выполняются следующие условия:

• Для каждой пары целых чисел \((i,j)\), если \(i\) и \(j\) взаимно просты, то \(a_i \neq a_j\).
• Максимальное значение всех \(a_i\) должно быть минимальным (то есть как можно меньшим).

Два натуральных числа называются взаимно простыми, если их наибольший общий делитель равен \(1\).

Авторы загадали массив \(a\), состоящий из \(n\) целых чисел; каждое число не меньше \(2\) и не больше \(2 \cdot 10^5\). Вы не знаете его, но Вы знаете массив \(b\), который был получен из массива \(a\) при помощи следующей последовательности операций:

1. Сначала весь массив \(b\) равен массиву \(a\);
2. Затем для каждого \(i\) от \(1\) до \(n\):
   • если \(a_i\) является простым числом, тогда число \(p_{a_i}\) добавляется в массив \(b\), где \(p\) — бесконечная последовательность простых чисел (\(2, 3, 5, \dots\));
   • иначе (если \(a_i\) не является простым числом), наибольший делитель \(a_i\), не равный \(a_i\), добавляется в \(b\);
3. Затем получившийся массив длины \(2n\) перемешивается и дается Вам во входных данных.

Здесь \(p_{a_i}\) означает \(a_i\)-е простое число. Первое простое число \(p_1 = 2\), второе простое число \(p_2 = 3\), и так далее.

Ваша задача — восстановить любой подходящий массив \(a\), который формирует заданный массив \(b\). Гарантируется, что ответ существует (таким образом, массив \(b\) получен из какого-либо подходящего массива \(a\)). Если существует несколько возможных ответов, Вы можете вывести любой.

Пусть \(f_{x} = c^{2x-6} \cdot f_{x-1} \cdot f_{x-2} \cdot f_{x-3}\) для \(x \ge 4\).

Вам даны \(n\), \(f_{1}\), \(f_{2}\), \(f_{3}\) и \(c\). Найдите \(f_{n} \bmod (10^{9}+7)\).

Мадам Ковариан украла новорожденную Мелоди Понд у её родителей, чтобы та стала оружием молчания в крестовом походе против Доктора. Мадам Ковариан изменила имя Мелоди на Ривер Сонг, что дало ей новую личность и позволило убить Одиннадцатого Доктора.

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

Первая хеш-функция, которую она рассматривает, выглядит следующим образом:

Предположим, что даны положительные целые числа \((x, y)\), тогда она определяет \(H(x,y):=x^2+2xy+x+1\).

Теперь, Хайди интересуется, является ли данная функция обратимой. В частности, у неё есть целое положительное \(r\), не могли бы вы найти пару \((x, y)\) (целые положительные числа), такие что \(H(x, y) = r\)?

Если существуют несколько таких пар, то выведите пару с минимальным \(x\). Если ни одной такой пары не существует, то выведите «NO».

Теперь Хайди готова взломать хеш-функцию Мадам Ковариан.

Мадам Ковариан пользуется весьма сложным набором правил для замены имён. Два имени могут быть заменены друг на друга только если следующая хеш-функция на них приводит к коллизии. Однако, хеш-функция параметризована, так что всегда можно подобрать набор параметров, который приводит к коллизии. Хайди решила воспользоваться этим в свою пользу.

Пусть даны строки \(w_1\) и \(w_2\) одинаковой длины \(n\), состоящей из строчных латинских букв, и целое число \(m\).

Рассмотрим стандартный полиномиальный хеш:

\(H_p(w) := \left( \sum_{i=0}^{|w|-1} w_i r^i \right) \mbox{mod}(p)\)

Где \(p\) некоторое простое, а \(r\) это некоторое целое число, такое что \(2\leq r \leq p-2\).

Вам нужно найти \(r\) и простое число \(p\) (\(m \leq p \leq 10^9\)), такие что \(H_p(w_1) = H_p(w_2)\).

Строки \(w_1\) и \(w_2\) выбраны случайно и независимо среди всех строк длины \(n\), состоящих из строчных латинских букв.

Tokitsukaze играет в «побег из комнаты», разработанный SkywalkerT. В этой игре она должна найти скрытые подсказки в комнате, чтобы раскрыть способ побега.

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

• Дверь можно будет открыть только после того, как будут введены \(n\) возможных различных паролей.
• Пароли должны быть целыми числами от \(0\) до \((m - 1)\);
• Пароль не может быть равен \(x\) (\(0 \leq x < m\)), если \(x\) и \(m\) не являются взаимно простыми числами (т.е. \(x\) и \(m\) имеют некоторый общий делитель больший одного);
• Пароль не может быть равен \(x\) (\(0 \leq x < m\)), если существуют неотрицательные целые числа \(e\) и \(k\) такие, что \(p^e = k m + x\), где \(p\) — секретное число;
• Любое целое число, не нарушающее описанных выше правил, может являться паролем.
• Несколько целых чисел спрятаны в комнате, однако только одно из них может являться числом \(p\).

К счастью, она узнала, что \(n\) и \(m\) записаны в замке. Тем не менее, Tokitsukaze расстроена тем, что она не очень хороша в математике. Теперь, когда она нашла число, которое может являться числом \(p\), она хочет, чтобы Вы помогли ей найти \(n\) возможных паролей или определить, что данное число не может быть числом \(p\).

Эта задача отличается от следующей исключительно наличием ограничения на равную длину всех чисел \(a_1, a_2, \dots, a_n\). На самом деле эта задача является подзадачей D2 из этого же контеста, и решение D2 решает эту подзадачу в том числе.

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

Определим функцию, чередующую цифры двух чисел, \(f(a_1 a_2 \dots a_{p - 1} a_p, b_1 b_2 \dots b_{q - 1} b_q)\), где \(a_1 \dots a_p\) и \(b_1 \dots b_q\) — цифры двух чисел в десятичной системе счисления, записанные без ведущих нулей.

Иными словами, функция \(f(x, y)\) перемешивает цифры чисел \(x\) и \(y\) выписывая их по очереди от младщих цифр к старшим, начиная с числа \(y\). Результат функции тоже строится справа налево (то есть от младших цифр к старшим). Если цифры одного из аргументов закончились, то выписываются оставшиеся цифры другого аргумента. Ознакомьтесь с примерами и формальным определением функции.

Например: \(\)f(1111, 2222) = 12121212\(\) \(\)f(7777, 888) = 7787878\(\) \(\)f(33, 44444) = 4443434\(\) \(\)f(555, 6) = 5556\(\) \(\)f(111, 2222) = 2121212\(\)

Формально:

• если \(p \ge q\), то \(f(a_1 \dots a_p, b_1 \dots b_q) = a_1 a_2 \dots a_{p - q + 1} b_1 a_{p - q + 2} b_2 \dots a_{p - 1} b_{q - 1} a_p b_q\);
• если \(p < q\), то \(f(a_1 \dots a_p, b_1 \dots b_q) = b_1 b_2 \dots b_{q - p} a_1 b_{q - p + 1} a_2 \dots a_{p - 1} b_{q - 1} a_p b_q\).

Мишаня дал вам массив из \(n\) целых чисел \(a_i\). Все числа в этом массиве имеют равную длину (то есть состоят из одинакового количества цифр). Помогите ребятам посчитать \(\sum_{i = 1}^{n}\sum_{j = 1}^{n} f(a_i, a_j)\) по модулю \(998\,244\,353\).

Дан массив из \(n\) чисел. Требуется разбить все числа на два множества таким образом, чтобы НОД всех чисел первого множества был равен единице и НОД всех чисел второго множества был равен единице.

НОД множества чисел — наибольшее целое число, делящее все числа из множества.

Оба множества должны быть непустыми.

Гильдон проводит эксперименты с интересной машиной под названием Graph Traveler. В этой машине есть ориентированный граф из \(n\) вершин, пронумерованных от \(1\) до \(n\). \(i\)-я вершина имеет \(m_i\) выходящих ребер, они обозначаются \(e_i[0]\), \(e_i[1]\), \(\ldots\), \(e_i[m_i-1]\), где каждый элемент обозначает номер вершины конца ребра. В графе могут быть кратные ребра и петли. Кроме того, в каждой вершине \(i\) написано некоторое целое число \(k_i\).

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

1. Гильдон выбирает вершину, с которой начнет путь, а также некоторое начальное целое число. Запомним это число в переменную \(c\).
2. Когда Гильдон приходит в вершину \(i\), а также, в начале, если путь начинается с вершины \(i\), он добавляет значение \(k_i\) к \(c\).
3. Следующая вершина пути — это \(e_i[x]\), где \(x\) — такое целое число \(0 \le x \le m_i-1\), что \(x \equiv c \pmod {m_i}\). Гильдон переходит в эту следующую вершину и возвращается на шаг 2.

Ясно, что такой путь никогда не кончается, потому что шаги 2 и 3 будут повторяться бесконечное число раз.

Например, предположим, что Гильдон начинает в вершине \(1\) с \(c = 5\), при этом \(m_1 = 2\), \(e_1[0] = 1\), \(e_1[1] = 2\), \(k_1 = -3\). Сразу после того, как он начинает в вершине \(1\), \(c\) становится равным \(2\). Так как единственное целое число \(x\) (\(0 \le x \le 1\)) такое, что \(x \equiv c \pmod {m_i}\), это \(0\), то Гильдон пойдет в вершину \(e_1[0] = 1\). После того как он попадет в вершину \(1\) снова, \(c\) станет равной \(-1\). Единственное целое число \(x\), удовлетворяющее сравнению, есть \(1\), поэтому он идет в вершину \(e_1[1] = 2\), и так далее.

Так как Гильдон достаточно любознательный, он хочет спросить у вас \(q\) вопросов. Каждый раз он хочет узнать, сколько различных вершин он посетит бесконечное число раз, если он начнет с определенной вершины с определенным числом \(c\). Обратите внимание, что не нужно учитывать вершины, которые будут посещены только конечное число раз.

Вам даны два целых числа \(n\) и \(k\).

Вам нужно построить \(k\) правильных многоугольников с общей описанной окружностью с различными количествами сторон \(l\) от \(3\) до \(n\).

Изображение к первому примеру.

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

Петя любит счастливые числа. Всем известно, что счастливыми являются положительные целые числа, в десятичной записи которых содержатся только счастливые цифры 4 и 7. Например, числа 47, 744, 4 являются счастливыми, а 5, 17, 467 — не являются.

Однажды во сне Петя увидел лексикографически k-ую перестановку целых чисел от 1 до n. Определите, сколько счастливых чисел стоит в этой перестановке на позициях, номера которых также являются счастливыми числами.

Петя любит счастливые числа. Всем известно, что счастливыми являются положительные целые числа, в десятичной записи которых содержатся только счастливые цифры 4 и 7. Например, числа 47, 744, 4 являются счастливыми, а 5, 17, 467 — не являются.

Петя называет число почти счастливым, если оно делится без остатка на какое-либо счастливое число. Помогите ему узнать, является ли заданное число n почти счастливым?

Мальчик Дима подарил Ульяне на день рождения множество \(B\), состоящее из положительных целых чисел. Однако он не учел, что Ульяна терпеть не может множества, а больше всего на свете любит двудольные графы!

Ульяна уже была готова расстроиться, но её друг Леша сказал, что может построить неориентированный граф с помощью этого множества следующим образом: рассмотрим все целые числа как вершины графа и соединим ребрами все \(i\) и \(j\) такие, что \(|i - j|\) принадлежит \(B\).

К сожалению, граф, построенный по множеству \(B\) не очень нравится Ульяне. Леша решил исправить ситуацию и хочет незаметно выкинуть из \(B\) несколько чисел так, чтобы граф, построенный на новом множестве был двудольным. Сложность этой задачи заключается в том, что граф, с которым придется работать Леше, содержит бесконечное число вершин и ребер! Одному с такой задачей не справиться, поэтому Леша просит Вас о помощи. Напишите программу, которая удаляет из \(B\) минимальное по размеру подмножество чисел так, чтобы граф, построенный на оставшемся множестве стал двудольным.

Напомним, что граф называется двудольным, если вершины можно разбить на 2 множества так, что не существует ребер между вершинами из одного множествами.

Вам дано \(n\) целых положительных чисел \(a_1, \ldots, a_n\) и целое \(k \geq 2\). Посчитайте количество пар \(i, j\), таких что \(1 \leq i < j \leq n\), а также существует целое \(x\), такое что \(a_i \cdot a_j = x^k\).

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

Пусть \(prime(x)\) будет множеством целочисленных простых делителей числа \(x\). Например, \(prime(140) = \{ 2, 5, 7 \}\), \(prime(169) = \{ 13 \}\).

Пусть \(g(x, p)\) будет максимальное число вида \(p^k\), где \(k\) — целое число, такое, что \(x\) делится на \(p^k\). Например:

• \(g(45, 3) = 9\) (\(45\) делится на \(3^2=9\), но не на \(3^3=27\)),
• \(g(63, 7) = 7\) (\(63\) делится на \(7^1=7\), но не на \(7^2=49\)).

Пусть \(f(x, y)\) будет произведением \(g(y, p)\) для всех \(p\), которые содержатся в множестве \(prime(x)\). Например:

• \(f(30, 70) = g(70, 2) \cdot g(70, 3) \cdot g(70, 5) = 2^1 \cdot 3^0 \cdot 5^1 = 10\),
• \(f(525, 63) = g(63, 3) \cdot g(63, 5) \cdot g(63, 7) = 3^2 \cdot 5^0 \cdot 7^1 = 63\).

Даны числа \(x\) и \(n\). Найдите \(f(x, 1) \cdot f(x, 2) \cdot \ldots \cdot f(x, n) \bmod{(10^{9} + 7)}\).

Вам заданы два целых числа \(x\) и \(y\) (гарантируется, что \(x > y\)). Вы можете выбрать любое простое целое число \(p\) и вычесть его любое количество раз из \(x\). Можно ли сделать \(x\) равным \(y\)?

Напомним, что простым называется целое положительное число, которое имеет ровно два положительных делителя: \(1\) и само это целое число. Последовательность простых чисел начинается с \(2\), \(3\), \(5\), \(7\), \(11\).

Ваша программа должна ответить на \(t\) независимых тестов.

Совсем недавно закончился футбольный сезон в Берляндии. В каждом футбольном матче в Берляндии участвуют по две команды. Результатом матча может быть победа одной из команд, либо ничья. Победившая в матче команда получает \(w\) очков, а проигравшая команда получает \(0\) очков. Если результат игры ничейный, то обе команды получают по \(d\) очков.

Владелец команды столицы Берляндии захотел подвести итоги сезона, но все данные об играх его команды были утеряны. Осталась лишь информация о том, что команда столицы Берляндии провела за сезон \(n\) матчей, в которых набрала \(p\) очков.

Перед вами стоит задача определить три целых числа \(x\), \(y\) и \(z\) — сколько матчей выиграла, сыграла вничью и проиграла команда столицы Берляндии. Если подходящих ответов несколько, вы можете вывести любой из них. Если не существует ни одной подходящей тройки \((x, y, z)\), сообщите об этом.

Это — упрощённая версия задачи. В этой версии, \(1 \le n \le 10^5\) и \(0 \le a_i \le 1\). Вы можете взламывать эту задачу только тогда, когда решите и заблокируете обе версии.

Приближается Рождество, и наш главный герой, Боб, готовит эффектный подарок для своей давней лучшей подруги Алисы. В этом году он решил приготовить \(n\) коробок шоколада, пронумерованных от \(1\) до \(n\). Изначально \(i\)-я коробка содержит \(a_i\) кусочков шоколада.

Поскольку Боб — типичный приятный парень, он не отправит Алисе \(n\) пустых ящиков. Другими словами, минимум одно число из \(a_1, a_2, \ldots, a_n\) является положительным. Поскольку Алиса не любит взаимно простые множества, она будет счастлива, только если существует какое-то целое число \(k > 1\), такое, что количество кусочков в каждой коробке делится на \(k\). Обратите внимание, что Алиса не будет возражать, если будут какие-то пустые коробки.

Чарли, парень Алисы, также является вторым лучшим другом Боба, поэтому он решает помочь Бобу, переставляя кусочки шоколада. За одну секунду Чарли может взять кусок в \(i\)-й коробке, и поместить его либо в \(i-1\)-ю коробку или \(i+1\)-ю коробку (если такие коробки существуют). Конечно, он хочет помочь своему другу как можно быстрее. Поэтому он просит вас подсчитать минимальное количество секунд, которое понадобится ему, чтобы сделать Алису счастливой.

Вам задано число \(x\), представленное в виде произведения \(n\) своих простых делителей \(p_1 \cdot p_2, \cdot \ldots \cdot p_n\). Пусть \(S\) — это множество всех положительных целых делителей числа \(x\) (включая \(1\) и само число \(x\)).

Назовем множество (set) целых чисел \(D\) хорошим тогда (и только тогда), когда не существует пары \(a \in D\), \(b \in D\) таких, что \(a \ne b\) и \(a\) делит \(b\).

Найдите хорошее подмножество \(S\) с максимально возможным размером. Так как ответ может быть очень большим, выведите размер подмножества по модулю \(998244353\).

На всеми известной тестирующей системе MathForces устраивается розыгрыш \(n\) единиц рейтинга. Раздача рейтинга будет происходить по следующему алгоритму: если в мероприятии принимает участие \(k\) участников, то \(n\) рейтинга поровну распределяется между ними и округляется в сторону ближайшего меньшего целого числа. По окончании распределения может остаться неиспользованный рейтинг — он не достаётся никому из участников.

К примеру, если \(n = 5\) и \(k = 3\), то каждый участник получит \(1\) единицу рейтинга, а также \(2\) единицы рейтинга останутся неиспользованными. Если же \(n = 5\), а \(k = 6\), то ни у кого из участников не увеличится рейтинг.

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

Например, если \(n=5\), то искомый ответ равен последовательности \(0, 1, 2, 5\). Каждое из значений последовательности (и только они) может быть получено как \(\lfloor n/k \rfloor\) для некоторое подходящего целого положительного \(k\) (где \(\lfloor x \rfloor\) — округлённое вниз значение \(x\)): \(0 = \lfloor 5/7 \rfloor\), \(1 = \lfloor 5/5 \rfloor\), \(2 = \lfloor 5/2 \rfloor\), \(5 = \lfloor 5/1 \rfloor\).

Напишите программу, которая по заданному \(n\) находит последовательность всех возможных приращений рейтинга.

Пусть \(a\) — матрица размера \(r \times c\), в каждой ячейке которой записано положительное целое число (эти числа не обязательно различны). Строки матрицы пронумерованы от \(1\) до \(r\), а столбцы — от \(1\) до \(c\). Мы можем построить массив \(b\), состоящий из \(r + c\) целых чисел, следующим образом: для каждого \(i \in [1, r]\) обозначим за \(b_i\) наибольший общий делитель всех чисел в \(i\)-й строке, а для каждого \(j \in [1, c]\) обозначим за \(b_{r+j}\) наибольший общий делитель всех чисел в \(j\)-м столбце.

Назовем матрицу разнообразной, если все \(r + c\) чисел \(b_k\) (\(k \in [1, r + c]\)) попарно различны.

Назовем модулем матрицы максимальное число среди \(b_k\).

Например, рассмотрим следующую матрицу:

Построим массив \(b\):

1. \(b_1\) — наибольший общий делитель \(2\), \(9\) и \(7\), он равен \(1\);
2. \(b_2\) — наибольший общий делитель \(4\), \(144\) и \(84\), он равен \(4\);
3. \(b_3\) — наибольший общий делитель \(2\) и \(4\), он равен \(2\);
4. \(b_4\) — наибольший общий делитель \(9\) и \(144\), он равен \(9\);
5. \(b_5\) — наибольший общий делитель \(7\) и \(84\), он равен \(7\).

Итак, \(b = [1, 4, 2, 9, 7]\). Все значения в этом массиве различны, поэтому матрица является разнообразной. Модулем матрицы является число \(9\).

Для заданных \(r\) и \(c\) найдите разнообразную матрицу с минимально возможным модулем. Если таких матриц несколько, найдите любую из них. Если решения нет, выведите единственное целое число \(0\).

Сегодня Осама вручил Фади целое число \(X\), а Фади стало интересно, какое минимальное значение может принимать \(max(a, b)\) таких, что \(LCM(a, b)\) равен \(X\). \(a\) и \(b\) должны быть положительными целыми числами.

\(LCM(a, b)\) — это наименьшее положительное целое число, которое делится и на \(a\), и на \(b\). Например, \(LCM(6, 8) = 24\), \(LCM(4, 12) = 12\), \(LCM(2, 3) = 6\).

Разумеется, Фади сразу нашел ответ. Сможете ли вы найти любую такую пару прямо как Фади?

«Всё было спланировано, Никаких больше скрытых забот. Состояние Цитуса тоже совершенно..»

Текущее время...... 00:01:12......

Время пришло.

Образцов эмоций теперь достаточно. Прошло почти три года, и пришло время для Айви разбудить свою связанную сестру Ванессу.

Система внутри библиотеки A.R.C. может быть представлена как неориентированный граф с бесконечным числом обрабатывающих вершин, пронумерованных последовательными положительными целыми числами (\(1, 2, 3, \ldots\)). Вершина с номером \(x\) (\(x > 1\)) напрямую соединена с вершиной с номером \(\frac{x}{f(x)}\), где \(f(x)\) обозначает наименьший простой делитель \(x\).

Разум Ванессы разделён на \(n\) фрагментов. Спустя более 500 лет в коме, фрагменты несколько подраскидало: \(i\)-й фрагмент теперь находится в вершине с номером \(k_i!\) (факториал \(k_i\)).

Чтобы максимизировать шансы успешного пробуждения, Айви хочет разместить образцы эмоций в вершине \(P\), такой что суммарная длина всех путей от каждого фрагмента до \(P\) является минимально возможной. В случае если несколько фрагментов расположены в одной и той же вершине, путь от них до \(P\) учитывается несколько раз.

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

Возможно ли такое же для простого смертного как вы?

Для простоты, найдите минимальную суммарную длину путей от каждого фрагмента до оптимальной вершины \(P\).