Вам даны два натуральных числа \(d\) и \(p\), \(p\) простое.
Кроме того у вас есть загадчный вычислитель. Вычислитель содержит ячейки памяти, каждая ячейка содержит число от \(0\) до \(p-1\). Поддерживаются две инструкции, сложение и возведение в степень \(d\). Обе операции производятся \(\textbf{по модулю}\) \(p\).
Ячейки памяти пронумерованы числами \(1, 2, \dots, 5000\). Изначально ячейки \(1\) и \(2\) содержат числа \(x\) и \(y\) соответственно (\(0 \leqslant x, y \leq p - 1\)). Все остальные ячейки заполнены единицами.
Вы не имеете доступа к числам напрямую, и Вам \(\textbf{неизвестны}\) точные значения \(x\) и \(y\). Ваша задача — написать программу с использованием доступных инструкций, вычисляющую произведение \(xy\) по модулю \(p\) в какой-нибудь ячейке. Программа должна работать для всех возможных \(x\) и \(y\).
Инструкция сложения вычисляет сумму значений в двух ячейках и записывает в третью. Эта инструкция кодируется строкой "+ e1 e2 to", что означает запись суммы значений в ячейках e1 и e2 в ячейку to. Любые из номеров e1, e2, to могут совпадать.
Вторая инструкция вычисляет значение \(d\)-й степени числа в ячейке, и записывает это значение в другую ячейку. Эта инструкция кодируется строкой "^ e to". Значения e и to могут совпадать, в этом случае значение в ячейке будет перезаписано.
Последняя инструкция — это специальная инструкция возврата. Она кодируется строкой "f target". Это означает, что результат \(xy \bmod p\) получен в ячейке target. Эта инструкция должна быть последней.
Найдите последовательность инструкций, получающую \(xy \bmod p\) и использующую не более \(5000\) инструкций (считая инструкцию возврата).
Гарантируется, что при данных ограничениях решение существует.
Примечание
В этой задаче отсутствуют тесты из условия. Пример вывода приведен ниже. Обратите внимание, что этот вывод не является решением ни для какого теста, и нужен только для того, чтобы продемонстрировать формат вывода.
\(\texttt{+ 1 1 3}\\ \texttt{^ 3 3}\\ \texttt{+ 3 2 2}\\ \texttt{+ 3 2 3}\\ \texttt{^ 3 1}\\ \texttt{f 1}\)
Ниже приведено пошаговое описание работы программы:
\(\begin{array}{|c|c|c|c|} \hline \texttt{} & \text{ячейка 1} & \text{ячейка 2} & \text{ячейка 3} \\
\hline \text{исходно} & x & y & 1 \\ \hline \texttt{+ 1 1 3} & x & y & 2x \\ \hline
\texttt{^ 3 3} & x & y & (2x)^d \\ \hline
\texttt{+ 3 2 2} & x & y + (2x)^d & (2x)^d \\ \hline
\texttt{+ 3 2 3} & x & y + (2x)^d & y + 2\cdot(2x)^d \\ \hline
\texttt{^ 3 1} & (y + 2\cdot(2x)^d)^d & y + (2x)^d & y + 2\cdot(2x)^d \\ \hline
\end{array}\)
Пусть \(d = 2\) and \(p = 3\). Поскольку при \(x = 0\) и \(y = 1\) возвращаемый результат равен \(1 \neq 0 \cdot 1 \bmod 3\), программа была оценена как неверная.