CF1060H.Sophisticated Device

You are given integers $d$ and $p$, $p$ is prime.

Also you have a mysterious device. It has memory cells, each contains an integer between $0$ and $p-1$. Also two instructions are supported, addition and raising to the $d$-th power. $\textbf{Both are modulo}$ $p$.

The memory cells are numbered $1, 2, \dots, 5000$. Initially cells $1$ and $2$ contain integers $x$ and $y$, respectively ($0 \leqslant x, y \leq p - 1$). All other cells contain $\textbf{1}$s.

You can not directly access values in cells, and you $\textbf{don't know}$ values of $x$ and $y$ (but you know they are written in first two cells). You mission, should you choose to accept it, is to write a program using the available instructions to obtain the product $xy$ modulo $p$ in one of the cells. You program should work for all possible $x$ and $y$.

Addition instruction evaluates sum of values in two cells and writes it to third cell. This instruction is encoded by a string "+ e1 e2 to", which writes sum of values in cells e1 and e2 into cell to. Any values of e1, e2, to can coincide.

Second instruction writes the $d$-th power of a value in some cell to the target cell. This instruction is encoded by a string "^ e to". Values e and to can coincide, in this case value in the cell will be overwritten.

Last instruction is special, this is the return instruction, and it is encoded by a string "f target". This means you obtained values $xy \bmod p$ in the cell target. No instructions should be called after this instruction.

Provide a program that obtains $xy \bmod p$ and uses no more than $5000$ instructions (including the return instruction).

It is guaranteed that, under given constrains, a solution exists.

给你整数 $d$ 和 $p$，其中 $p$ 是质数。

你还拥有一台神秘设备。该设备具有内存单元，每个单元存储一个介于 $0$ 与 $p-1$ 之间的整数。设备支持两种指令：加法和求 $d$ 次幂，二者均对 $p$ 取模。

内存单元编号为 $1, 2, \dots, 5000$。初始时，单元 $1$ 和 $2$ 分别存有整数 $x$ 和 $y$（满足 $0 \leqslant x, y \leq p - 1$），其余所有单元均存有 1。

你无法直接读取各单元中的值，也不知道 $x$ 和 $y$ 的具体取值（但你知道它们分别存于前两个单元中）。你的任务——如果你选择接受——是仅使用上述两种指令，编写一段程序，使得某一个内存单元中最终存有乘积 $xy \bmod p$。该程序须对所有可能的 $x$ 和 $y$ 均成立。

加法指令计算两个单元中数值之和，并将结果写入第三个单元。该指令以字符串格式 "+ e1 e2 to" 编码，表示将单元 e1 与 e2 中的值相加，结果写入单元 to。e1、e2 和 to 的编号可以相同。

第二种指令将某个单元中数值的 $d$ 次幂写入目标单元。该指令以字符串 "^ e to" 编码。e 和 to 的编号可以相同；此时该单元中原有值将被覆盖。

最后一种指令为特殊指令：返回指令，以字符串 "f target" 编码。它表示你已在单元 target 中成功得到 $xy \bmod p$。此指令之后不得再调用任何其他指令。

请提供一个能计算出 $xy \bmod p$ 的程序，且总指令数（含返回指令）不超过 $5000$ 条。

题目保证在给定约束下，解一定存在。

The first line contains space-separated integers $d$ and $p$ ($2 \leqslant d \leqslant 10$, $d \lt p$, $3 \leqslant p \leqslant 10^9 + 9$, $p$ is prime).

第一行包含两个用空格分隔的整数 $d$ 和 $p$（$2 \leqslant d \leqslant 10$，$d \lt p$，$3 \leqslant p \leqslant 10^9 + 9$，且 $p$ 为质数）。

Output instructions, one instruction per line in the above format. There should be no more than $5000$ lines, and the last line should be the return instruction.

按上述格式输出指令，每行一条指令。指令总数不应超过 $5000$ 行，且最后一行应为返回指令。

This problem has no sample tests. A sample output is shown below. Note that this output is not supposed to be a solution to any testcase, and is there purely to illustrate the output format.

\texttt{+ 1 1 3}\\ \texttt{^ 3 3}\\ \texttt{+ 3 2 2}\\ \texttt{+ 3 2 3}\\ \texttt{^ 3 1}\\ \texttt{f 1}

Here's a step-by-step runtime illustration:

$\begin{array}{|c|c|c|c|} \hline \texttt{} & \text{cell 1} & \text{cell 2} & \text{cell 3} \\

\hline \text{initially} & 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}$

Suppose that $d = 2$ and $p = 3$. Since for $x = 0$ and $y = 1$ the returned result is $1 \neq 0 \cdot 1 \bmod 3$, this program would be judged as incorrect.

本题没有样例测试。下方展示了一个样例输出。请注意，该输出并非任何测试用例的正确解，仅用于说明输出格式。

\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$ 且 $p = 3$。当 $x = 0$、$y = 1$ 时，程序返回结果为 $1 \neq 0 \cdot 1 \bmod 3$，因此该程序将被判定为错误。