给定整数 $$$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{1}$$$s。
您无法直接访问单元格中的值,并且您 $$$\textbf{不知道}$$$ $$$x$$$ 和 $$$y$$$ 的值(但您知道它们写在前两个单元格中)。如果您选择接受,您的任务是使用可用指令编写一个程序,以在其中一个单元格中获取对 $$$p$$$ 取模 $$$xy$$$ 的乘积。您的程序应该适用于所有可能的 $$$x$$$ 和 $$$y$$$。
加法指令计算两个单元格中的值之和并将其写入第三个单元格。该指令由字符串“+ e1 e2 to”编码,它将单元格 e1 和 e2 中的值之和写入单元格 to 中。 e1、e2、to 的任何值都可以重合。
第二条指令将某个单元格中的值的 $$$d$$$ 次方写入目标单元格。该指令由字符串“^e to”编码。值 e 和 to 可以重合,在这种情况下,单元格中的值将被覆盖。
最后一条指令比较特殊,这是返回指令,它由字符串“f target”编码。这意味着您在单元格目标中获得了值 $$$xy \bmod p$$$ 。在此指令之后不应调用任何指令。
提供一个程序,获取$$$xy \bmod p$$$并且使用不超过$$$5000$$$指令(包括返回指令)。
保证在给定的约束下存在解。
输入
第一行包含空格分隔的整数 $$$d$$$ 和 $$$p$$$ ($$$2 \leqslant d \leqslant 10$$$、$$$d < p$$$、$$$3 \leqslant p \leqslant 10^9 + 9$$$、$$$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{cell 1} & \text{cell 2} & \text{cell 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{数组}$$$
假设 $$$d = 2$$$ 且 $$$p = 3$$$。由于$$$x = 0$$$ 和$$$y = 1$$$ 的返回结果为$$$1 \neq 0 \cdot 1 \bmod 3$$$,因此该程序将被判断为不正确。