Даны два натуральных числа $$$a$$$ и $$$b$$$. Требутся найти количество различных натуральных $$$x$$$, удовлетворяющих равенству НОК$$$(x, a) = b$$$.

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

У вас имеется $$$N$$$ целых положительных чисел $$$a_1, a_2, \ldots, a_N$$$. От вас требуется переупорядочить данные числа таким образом, чтобы для любых $$$a_i$$$ и $$$a_{i + 1}$$$ были выполнены условия:

1. Пусть $$$c_1, c_2, \ldots, c_k$$$ — всевозможные положительные делители числа $$$a_i$$$, причем $$$c_i \lt c_{i + 1}$$$. Аналогично $$$d_1, d_2, \ldots, d_l$$$ — делители числа $$$a_{i + 1}$$$. Должно быть верно, что либо $$$k \lt l$$$, либо $$$k = l$$$, и при этом для любого $$$j$$$ верно, что $$$c_j \leq d_j$$$.
2. $$$a_i$$$ AND $$$a_{i + 1} = a_i$$$, где AND — операция побитового «И».

Костя отыскал у себя дома $$$N$$$ кубиков и принялся играть в одну увлекательную игру: он захотел воспользоваться находкой и построить максимально высокую башню!

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

Его другу Мише такая игра показалась скучной, и он решил в неё вмешаться. После того, как Костя совершит очередное действие и запишет на лист количество кубиков в новой башне, Миша будет делать одно из двух действий:

• Не вмешиваться в игру и позволить Косте продолжать строительство башни.
• Разрушить башню, которая на данный момент находится на столе и забрать все кубики, из которых состояла башня, себе. Если Миша забрал себе некоторые кубики, он уже ни за что не отдаст их Косте.

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

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

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

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

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

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

Формально, возможны четыре варианта развития событий:

1. Программа является синтаксически некорректной. В данном случае результатом считается Compilation error.
2. Программа является синтаксически корректной, однако завершается с ошибкой (например, POP из пустого стека). В этом случае результатом считается Runtime error.
3. Программа является синтаксически корректной, однако не успевает завершиться за указанное количество тактов. В этом случае результатом считается Time limit exceeded.
4. Программа является синтаксически корректной и завершается без ошибок не более, чем за указанное количество тактов. В этом случае результатом считается Accepted. В данном случае необходимо помимо вердикта вывести конечное состояние стека.

Ниже приведены выдержки из задачи прошлого года, описывающие машину, а также допустимые операции и их синтаксис. Если вы хорошо помните задачу, можете продолжать чтение с раздела «Входные данные».

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

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

Список доступных инструкций приведен ниже. RTE (Runtime 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 не является условием)

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

IF cond THEN
BEGIN
    body
END

Цикл while:

WHILE cond DO
BEGIN
    body
END

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

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

Каждая инструкция (а также проверки условия для условного оператора и цикла) выполняется 1 такт.

Верхний регистр в названиях инструкций важен.

У Егора есть любимое число $$$n$$$. Он обожает решать различные задачи, связанные с этим числом. Сегодня он подумал, что хочет найти максимальное целое число $$$m \leq n$$$, такое что двоичная запись числа $$$m$$$ оканчивается ровно на $$$k$$$ нулей.

Однажды одна из команд довольно неклассического университета участвовала в сборах по программированию. На одном из контестов была предложена задача с довольно большим условием, которое принялись одновременно читать двое из трех участников команды — гроссмейстер-геометр Захар и специалист в области ASCII-графики и парсеров Майк. Через некоторое время ребята прочитали условие, обсудили его и выяснили, что задача является довольно простой, и через пятнадцать минут решение уже было готово и отправлено в тестирующую систему. Однако, по какой-то причине, команду ожидала неудача — «Неправильный ответ на тесте 4».

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

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

Дан неориентированный граф, состоящий из $$$n$$$ вершин и $$$m$$$ ребер, соединяющих некоторые пары вершин.

Назовем последовательность вершин $$$v_1, v_2, \ldots, v_k$$$ простым путем, если для любых $$$i \neq j$$$ верно, что $$$v_i \neq v_j$$$, а также для любого $$$i = 1 \ldots k - 1$$$ в графе есть ребро, соединяющее вершины $$$v_i$$$ и $$$v_{i + 1}$$$.

Длиной простого пути будем считать количество вершин в нем.

Два простых пути $$$v_1, v_2, \ldots, v_k$$$ и $$$u_1, u_2, \ldots, u_l$$$ считаются различными, если $$$k \neq l$$$, либо $$$k = l$$$ и существует такое $$$i$$$, что $$$v_i \neq u_i$$$.

Назовем три различных простых пути $$$3$$$-связанными, если выполнены следующие условия:

1. Первые вершины путей совпадают;
2. Последние вершины путей совпадают;
3. Если рассмотреть множество всех вершин данных путей, за исключением первой и последней, то найдется вершина, которая встречается более, чем в одном из трех путей.

Обратите внимание, что $$$3$$$-связанные пути не обязаны иметь одинаковую длину.

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

Требуется для каждого $$$l = 1 \ldots n$$$ вычислить количество различных простых путей длины $$$l$$$ в данном графе.

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

В бою будут участвовать $$$n$$$ орков, которых необходимо разделить на отряды. Саурфанг считает, что важны не количество или численность отрядов, а высокий боевой дух. Для каждого орка известно, что сам он пойдет в атаку с боевым духом $$$a_i$$$. Однако если орка воодушевит его командир, то он уже будет сражаться более яростно с боевым духом $$$b_i$$$. Но здесь возникает небольшая сложность...

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

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

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

Представьте, что у вас есть прямоугольная сетка размера $$$N \times M$$$, разделенная на квадраты $$$1 \times 1$$$. От вас требуется посчитать, сколькими способами можно выбрать на данной сетке четыре узла таким образом, чтобы они образовывали невырожденный параллелограмм.

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

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

1. Вы можете улучшить уровень навыков вашего персонажа несколько раз. За каждое улучшение вы обязаны отдать некоторое ненулевое количество очков опыта. Сколько именно очков отдавать за каждое улучшение — решать вам.
2. Вы обязаны потратить все накопившиеся $$$N$$$ очков опыта.
3. Представим, что вы улучшили навыки персонажа $$$S$$$ раз, отдав за каждое улучшение $$$a_1, a_2, \ldots, a_S$$$ очков опыта, соответственно. Если найдутся такие $$$l$$$ и $$$r$$$, что $$$1 \leq l \leq r \leq S$$$ и $$$a_l + a_{l + 1} + \ldots + a_r = K$$$, то ваш персонаж моментально погибнет — это необычное свойство связано с черной магией, не пытайтесь понять, как это работает.
4. Конечно же, вы хотите улучшить навыки персонажа как можно больше раз.

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

В данной задаче вам предстоит окунуться в увлекательный мир строк!

Пусть имеется алфавит, состоящий из строчных латинских букв. Назовем номером буквы ее порядковый номер в алфавите и будем обозначать это как $$$num(a)$$$. Таким образом, $$$num($$$a$$$) = 1$$$, $$$num($$$b$$$) = 2$$$, а $$$num($$$z$$$) = 26$$$.

Пусть у нас имеется две строки $$$s$$$ и $$$t$$$ одинаковой длины $$$n$$$: $$$|s| = |t| = n$$$. Будем обозначать $$$i$$$-й символ строки $$$s$$$ как $$$s_i$$$.

Введем функцию $$$f(s, t)$$$, которая вычисляется по следующей формуле: $$$$$$f(s, t) = \sum\limits_{i=1}^{n} |num(s_i) - num(t_i)|$$$$$$

Дана строка $$$s$$$ длины $$$n$$$. Обозначим подстроку строки $$$s$$$, начинающуюся с $$$i$$$-го символа строки и заканчивающуюся $$$j$$$-м символом строки, как $$$s[i \ldots j]$$$.

От вас требуется посчитать следующую величину: зафиксируем некоторую длину подстроки $$$k = 1 \ldots n$$$. Рассмотрим все пары подстрок строки $$$s$$$, имеющих длину $$$k$$$. Нужно вычислить сумму значений функции $$$f$$$ от каждой пары подстрок.

Формально, нужно вычислить следующую сумму:

$$$$$$\sum\limits_{k=1}^{n} \sum\limits_{1 \leq i, j \leq n - k + 1} f(s[i \ldots i+k-1], s[j \ldots j + k - 1])$$$$$$

Маша увлекается математикой и программированием, ее уже давно не удивить такими словами, как «Дерево отрезков», «Двойное тестирование», «Пересечение полуплоскостей», или, например, словом «Граф».

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

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

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

Обозначим за $$$C_k(n)$$$ количество всевозможных графов, состоящих из $$$n$$$ вершин, в которых нет ни одной вершины со степенью $$$k$$$. Маше стало интересно, каких графов больше: графов без вершин со степенью $$$0$$$, или же графов без вершин со степенью $$$n - 1$$$? Иными словами, Маша захотела вычислить разность $$$C_0(n) - C_{n - 1}(n)$$$ для некоторого выбранного $$$n$$$. Попробуйте сделать это и вы!

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

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

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

Пусть у нас имеются резисторы с сопротивлениями $$$R_1, R_2, \ldots, R_N$$$. Тогда при их последовательном соединении общее сопротивление полученной цепи будет равно: $$$$$$R = R_1 + R_2 + \ldots + R_N$$$$$$

Такая цепь изображена на рисунке ниже:

При параллельном соединении резисторов общее сопротивление цепи вычисляется по формуле: $$$$$$R = \dfrac{1}{\dfrac{1}{R_1} + \dfrac{1}{R_2} + \ldots + \dfrac{1}{R_N}}$$$$$$

Такая цепь изображена на рисунке ниже:

Представим теперь, что у нас имеется специализированный компьютер для расчетов, связанных с электрическими цепями. У этого компьютера есть $$$128$$$ регистров, в каждом из которых можно сохранить ровно одну электрическую цепь, состоящую только из резисторов. Регистры пронумерованы числами от $$$0$$$ до $$$127$$$. Изначально в регистре с номером $$$0$$$ записана элементарная цепь: один резистор с сопротивлением $$$R_0 = 1$$$. Все остальные регистры изначально пусты.

Перед началом работы вы можете заполнить некоторое количество регистров с номерами от $$$1$$$ до $$$127$$$ корректными электрическими цепями. Электрическая цепь является корректной для записи в регистр с номером $$$i$$$, если:

• Для конструирования данной цепи используются только операции последовательного и параллельного соединения некоторых других цепей;
• Все используемые при соединении цепи были получены в регистрах с номерами, меньшими, чем $$$i$$$ (включая регистр $$$0$$$).

Для удобства обозначим общее сопротивление цепи, полученной в $$$i$$$-м регистре, как $$$R_i$$$.

После того, как вы заполнили необходимое вам количество регистров, к вам будут поступать запросы. Входным параметром каждого запроса является значение сопротивления $$$R = \dfrac{x}{y}$$$. В качестве ответа на запрос вы должны сконструировать электрическую цепь, общее сопротивление которой в точности равно $$$R$$$. Для конструирования цепи вы можете использовать последовательные и параллельные соединения записанных в регистрах цепей. Более того, количество использованных цепей, сохраненных в регистрах, не должно быть слишком большим. Сможете ли вы справиться с поставленной задачей?

Для начала вы должны вывести целое число $$$t$$$ — количество регистров, которые вы собираетесь использовать ($$$1 \leq t \leq 128$$$). Это означает, что вы сможете воспользоваться регистрами с номерами от $$$0$$$ до $$$t - 1$$$.

После этого выведите $$$t$$$ строк, в каждой из которых выведите описание сконструированной цепи. Цепь, выведенная в $$$i + 1$$$-й строке, будет сохранена в регистр с номером $$$i$$$, после чего данную цепь можно будет использовать для построения новых цепей. Сопротивление данной цепи будет обозначено как $$$R_i$$$.

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

$$$\langle circuit \rangle~::=$$$ «R$$$i$$$»$$$~|~\langle series \rangle~|~\langle parallel \rangle$$$

$$$\langle series \rangle~::=$$$ «S(» $$$\langle circuit \rangle$$$ «,» $$$\langle circuit \rangle$$$ «)»

$$$\langle parallel \rangle~::=$$$ «P(» $$$\langle circuit \rangle$$$ «,» $$$\langle circuit \rangle$$$ «)»

При этом при построении цепи, сохраняемой в регистр с номером $$$i$$$, разрешается использовать $$$R_j$$$ только в случае $$$j \lt i$$$.

После этого вы должны считать число $$$q$$$ ($$$1 \leq q \leq 1\,000$$$) — количество запросов.

Для ответа на каждый запрос сначала считайте два целых числа: $$$x$$$ и $$$y$$$ ($$$1 \leq x \leq 10^{18}$$$, $$$1 \leq y \leq 10^{18}$$$). После этого выведите описание построенной цепи в описанной выше грамматике. Общее сопротивление полученной цепи должно быть равно $$$\dfrac{x}{y}$$$. При описании цепи разрешается использовать $$$R_i$$$ для всех $$$0 \leq i \lt t$$$.

Для всех построенных цепей, включая описание регистров, должны быть выполнены следующие ограничения. Описание цепи должно быть записано на одной строке. При описании цепи разрешается использовать сколько угодно пробелов, однако нельзя ставить пробелы между символом $$$R$$$ и номером регистра. Количество использованных $$$R_i$$$ в описании цепи не должно превышать $$$90$$$. Длина полученного выражения не должна превышать $$$10\,000$$$ символов.

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

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