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

Перед началом игры Леша достал из шкафа $$$N$$$ кубиков, после чего на каждом кубике написал число от $$$1$$$ до $$$N$$$. Разумеется, ни на каких двух кубиках Леша не написал одно и то же число.

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

Своим первым ходом Леша случайно равновероятно перемешивает все лежащие перед ним кубики и выкладывает их в ряд. После этого Полина во время своего хода сообщает ему, какие кубики лежат на своем месте. Будем говорить, что кубик с написанным на нем числом $$$A$$$ лежит на своем месте, если слева от него находятся ровно $$$A - 1$$$ кубиков. Во время всех следующих ходов Леша не будет трогать кубики, которые лежат на своем месте.

Далее Леша снова перемешивает все кубики, которые лежат не на своих местах, а Полина сообщает ему, какие из них оказались на своем месте. Игра продолжается до тех пор, пока все кубики не окажутся на своих местах.

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

Young wilderness explorers set off to their first expedition led by senior explorer Russell. Explorers went into a forest, set up a camp and decided to split into groups to explore as much interesting locations as possible. Russell was trying to form groups, but ran into some difficulties...

Most of the young explorers are inexperienced, and sending them alone would be a mistake. Even Russell himself became senior explorer not long ago. Each of young explorers has a positive integer parameter $$$e_i$$$ — his inexperience. Russell decided that an explorer with inexperience $$$e$$$ can only join the group of $$$e$$$ or more people.

Now Russell needs to figure out how many groups he can organize. It's not necessary to include every explorer in one of the groups: some can stay in the camp. Russell is worried about this expedition, so he asked you to help him.

Многие в детстве играют с кубиками, затем все в школе изучают геометрию и встречаются с такими простыми объектами, как параллелепипеды. Но ведь изучать геометрию в трехмерном пространстве — это так скучно! Даже четырехмерным пространством уже никого не удивишь! Поэтому в этой задаче мы предлагаем вам изучить параллелепипеды в $$$M$$$-мерном пространстве. Чувствуете, как интересно?

Определим $$$M$$$-мерный параллелепипед как набор отрезков $$$[a_1, b_1], [a_2, b_2], \ldots, [a_M, b_M]$$$, где $$$a_i \lt b_i$$$ для всех $$$i = 1 \ldots M$$$. Для простоты будем считать, что все $$$a_i$$$ и $$$b_i$$$ являются целыми.

Скажем, что точка с координатами $$$(x_1, x_2, \ldots, x_M)$$$ лежит внутри параллелепипеда, если выполнены неравенства:

Вам даны $$$N$$$ $$$M$$$-мерных параллелепипедов. Требуется посчитать, сколько точек с целочисленными координатами лежат внутри ровно $$$N-1$$$ параллелепипеда. Так как ответ может быть большим, выведите остаток от деления количества точек на число $$$998\,244\,353$$$.

Petya and Vasya are competing with each other in a new interesting game as they always do.

At the beginning of the game Petya has to come up with an array of $$$N$$$ positive integers. Sum of all elements in his array should be equal to $$$S$$$. Then Petya has to select an integer $$$K$$$ such that $$$0 \leq K \leq S$$$.

In order to win, Vasya has to find a non-empty subarray in Petya's array such that the sum of all selected elements equals to either $$$K$$$ or $$$S - K$$$. Otherwise Vasya loses.

You are given integers $$$N$$$ and $$$S$$$. You should determine if Petya can win, considering Vasya plays optimally. If Petya can win, help him to do that.

Let's define the following recurrence: $$$$$$a_{n+1} = a_{n} + minDigit(a_{n}) \cdot maxDigit(a_{n}).$$$$$$

Here $$$minDigit(x)$$$ and $$$maxDigit(x)$$$ are the minimal and maximal digits in the decimal representation of $$$x$$$ without leading zeroes. For examples refer to notes.

Your task is calculate $$$a_{K}$$$ for given $$$a_{1}$$$ and $$$K$$$.

Вокруг живописного круглого озера расположено $$$N$$$ домов на одинаковом расстоянии $$$D$$$ друг от друга. Михаил живет в одном из этих домов, во всех остальных домах живут его друзья. Все нравится Михаилу: и прекрасная природа, и добрые соседи, и мягкий климат, но и в эти места добрался коронавирус... И вот теперь жители самоизолировались, и могут выходить на прогулку только по одному человеку, при этом все остальные находятся в своих домах.

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

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

Like any unknown mathematician, Yuri has favourite numbers: $$$A$$$, $$$B$$$, $$$C$$$, and $$$D$$$, where $$$A \leq B \leq C \leq D$$$. Yuri also likes triangles and once he thought: how many non-degenerate triangles with integer sides $$$x$$$, $$$y$$$, and $$$z$$$ exist, such that $$$A \leq x \leq B \leq y \leq C \leq z \leq D$$$ holds?

Yuri is preparing problems for a new contest now, so he is very busy. That's why he asked you to calculate the number of triangles with described property.

The triangle is called non-degenerate if and only if its vertices are not collinear.

You have to restore the wall. The wall consists of $$$N$$$ pillars of bricks, the height of the $$$i$$$-th pillar is initially equal to $$$h_{i}$$$, the height is measured in number of bricks. After the restoration all the $$$N$$$ pillars should have equal heights.

You are allowed the following operations:

• put a brick on top of one pillar, the cost of this operation is $$$A$$$;
• remove a brick from the top of one non-empty pillar, the cost of this operation is $$$R$$$;
• move a brick from the top of one non-empty pillar to the top of another pillar, the cost of this operation is $$$M$$$.

You cannot create additional pillars or ignore some of pre-existing pillars even if their height becomes $$$0$$$.

What is the minimal total cost of restoration, in other words, what is the minimal total cost to make all the pillars of equal height?

This is an interactive problem.

We have hidden an integer $$$1 \le X \le 10^{9}$$$. You don't have to guess this number. You have to find the number of divisors of this number, and you don't even have to find the exact number: your answer will be considered correct if its absolute error is not greater than 7 or its relative error is not greater than $$$0.5$$$. More formally, let your answer be $$$ans$$$ and the number of divisors of $$$X$$$ be $$$d$$$, then your answer will be considered correct if at least one of the two following conditions is true:

• $$$| ans - d | \le 7$$$
• $$$\frac{1}{2} \le \frac{ans}{d} \le 2$$$

You can make at most 22 queries. One query consist of one integer $$$1 \le Q \le 10^{18}$$$. In response you will get $$$gcd(X, Q)$$$ — the greatest common divisor of $$$X$$$ and $$$Q$$$.

The number $$$X$$$ is fixed before all queries. In other words, interactor is not adaptive.

Let's call the process of guessing the number of divisors of number $$$X$$$ a game. In one test you will have to play $$$T$$$ independent games, that is, guess the number of divisors $$$T$$$ times for $$$T$$$ independent values of $$$X$$$.

To make a query print a line "? Q" ($$$1 \le Q \le 10^{18}$$$). After that read one integer $$$gcd(X, Q)$$$. You can make no more than 22 such queries during one game.

If you are confident that you have figured out the number of divisors of $$$X$$$ with enough precision, you can print your answer in "! ans" format. $$$ans$$$ have to be an integer. If this was the last game, you have to terminate the program, otherwise you have to start the next game immediately. Note that interactor doesn't print anything in response to you printing answer.

After printing a query do not forget to output end of line and flush the output. To do this, use:

• fflush(stdout) or cout.flush() in C++;
• System.out.flush() in Java;
• flush(output) in Pascal;
• stdout.flush() in Python;
• see documentation for other languages.

Дано $$$0 \le N \le 100$$$ целых неотрицательных чисел, выведите их сумму.

Эх, как было бы хорошо, если бы вам нужно было написать программу для решения такой задачи на C++ или Python...

У вас есть машина, память которой — это стек, элементы которого являются целыми числами. Количество элементов стека в данный момент мы будем обозначать как $$$sz$$$.

Напомним, что стек — это абстрактная структура данных, хранящая коллекцию элементов, и работающая по принципу LIFO (последним пришёл — первым вышел). Стек поддерживает две базовые операции: положить элемент на вершину стека, взять элемент с вершины стека. В качестве аналогии можно представить стопку тарелок: вы не можете оперировать с тарелками не на вершине стопки.

Список доступных инструкций приведен ниже. RTE (Run-Time Error) обозначает, что выполнение программы завершилось с ошибкой, вам следует избегать таких ситуаций.

• PUSHZ — положить на стек 0;
• POP — взять со стека $$$x$$$ (если $$$sz \lt 1$$$, то RTE);
• SWAP2 — взять со стека $$$x$$$, взять со стека $$$y$$$, положить на стек $$$x$$$, положить на стек $$$y$$$ (если $$$sz \lt 2$$$, то RTE);
• SWAP3 — взять со стека $$$x$$$, взять со стека $$$y$$$, взять со стека $$$z$$$, положить на стек $$$y$$$, положить на стек $$$x$$$, положить на стек $$$z$$$ (если $$$sz \lt 3$$$, то RTE);
• COPY — взять со стека $$$x$$$, положить на стек $$$x$$$, положить на стек $$$x$$$ (если $$$sz \lt 1$$$, то RTE);
• INC — взять со стека $$$x$$$, положить на стек $$$x+1$$$ (если $$$sz \lt 1$$$, то RTE);
• DEC — взять со стека $$$x$$$, положить на стек $$$x-1$$$ (если $$$sz \lt 1$$$, то RTE);
• ADD — взять со стека $$$x$$$, взять со стека $$$y$$$, положить на стек $$$x+y$$$ (если $$$sz \lt 2$$$, то RTE);
• SUB — взять со стека $$$x$$$, взять со стека $$$y$$$, положить на стек $$$x-y$$$ (если $$$sz \lt 2$$$, то RTE);

Также доступны условный оператор и цикл while. Чтобы их использовать, сначала нужно научиться задавать какие-то условия:

• EZ — TRUE если на вершине стека 0 (если $$$sz \lt 1$$$, то RTE);
• GZ — TRUE если на вершине стека положительное число (если $$$sz \lt 1$$$, то RTE);
• HAVE1, HAVE2 — TRUE если $$$sz \ge k$$$ (обратите внимание, что $$$k \in \{ 1, 2 \}$$$, HAVE3 не является условием)

К любому условию можно добавить NOT в начале, например NOT GZ (обратите внимание на пробел) TRUE если на вершине стека 0 или отрицательное число.

Условный оператор:

IF cond THEN
BEGIN
    body
END

Цикл while:

WHILE cond DO
BEGIN
    body
END

В обоих случаях cond — одно из условий, описанных выше, body — тело условного оператора или цикла — последовательность команд, которые будут выполнены, если cond=TRUE (один раз в случае условного оператора, или много раз в случае цикла). Циклы и условные операторы могут быть вложенными.

Вы должны написать программу для этой машины, котора решает следующую задачу:

Изначально стек был пуст. Числа $$$N, a_{1}, a_{2}, \ldots, a_{N}$$$ положили на стек в таком порядке (наверху стека лежит $$$a_{N}$$$, $$$N$$$ лежит в самом низу). После выполнения программы на вершине стека должно лежать число $$$a_{1} + a_{2} + \ldots + a_{N}$$$ (также в стеке могут лежать другие числа).

Гарантируется, что $$$0 \le N \le 100$$$, $$$0 \le a_{i}$$$. Каждая инструкция (а также проверки условия для условного оператора и цикла) выполняется 1 такт. Выполнение программы должно занимать не более $$$(N+22)^{2}$$$ тактов. В процессе выполнения программы не должно происходить RTE.