题目描述

你的任务是编写程序 polymul，生成一个用于乘法两个固定次数多项式的算法。

给定两个次数分别为 $N$ 和 $M$ 的多项式：

$$P(x)=a_0+a_1x+a_2x^2+\cdots+a_Nx^N,$$ $$Q(x)=b_0+b_1x+b_2x^2+\cdots+b_Mx^M.$$

一个算法 $A(N,M)$ 接收这两个多项式的系数作为输入，并输出 $N+M+1$ 个数：

$$c_0,c_1,\ldots,c_{N+M},$$

它们应当是多项式

$$R(x)=c_0+c_1x+\cdots+c_{N+M}x^{N+M}$$

的系数，并满足：

$$R(x)=P(x)\cdot Q(x)$$

对任意 $x$ 都成立。

这里的“算法”是一个由算术操作组成的列表，允许使用三种操作：加法 +、减法 -、乘法 *。每个操作作用于两个值，这两个值可以是：

• 输入系数 aK 或 bK；
• 之前步骤中计算出的中间值 iK；
• 常数 K。

算法示例

下面是一个乘法两个一次多项式的算法 $A(1,1)$：

步骤	说明
开始	当前可使用 a0, a1, b0, b1
= a0 * b0	计算中间值 i1 = a0 * b0
= a1 * b1	计算中间值 i2 = a1 * b1
= a0 * b1	计算中间值 i3 = a0 * b1
= a1 * b0	计算中间值 i4 = a1 * b0
= i3 + i4	计算中间值 i5 = (a0 * b1) + (a1 * b0)
= a0 * 34	计算中间值 i6 = a0 * 34，这是一个与结果无关的示例操作
o i1 i5 i2	输出 $c_0=i1,c_1=i5,c_2=i2$

你生成的多项式乘法算法不仅要正确，还要尽可能减少非平凡乘法的数量。

如果一次乘法中至少有一个操作数是常数，则称它为平凡乘法。否则称为非平凡乘法。

上面的算法使用了 $4$ 次非平凡乘法：

a0 * b0, a1 * b1, a0 * b1, a1 * b0

以及 $1$ 次平凡乘法：

a0 * 34

一个更好的 $A(1,1)$ 算法如下：

= a1 + a0
= b1 + b0
= i1 * i2
= a0 * b0
= a1 * b1
= i3 - i4
= i6 - i5
o i4 i7 i5

它只使用了 $3$ 次非平凡乘法。

为了避免浮点精度问题，所有计算都在模 $1\,000\,000\,007$ 意义下进行。也就是说，算法中的每个常数都必须是 $0$ 到 $1\,000\,000\,006$ 之间的整数。你输出的算法中的每个算术操作也都会按模 $1\,000\,000\,007$ 计算。

输入格式

输入只有一行，包含两个整数 $N,M$，表示需要相乘的两个多项式的次数。

输出格式

输出一个用于计算 $P(x)Q(x)$ 的算法。

除最后一行外，算法的每一行，即第 $L$ 行，格式必须为：

= S operation T

其中 operation 是 +、-、* 之一，S 和 T 可以是以下三类值之一：

• 输入系数 aK，其中 $0 \le K \le N$；
• 输入系数 bK，其中 $0 \le K \le M$；
• 中间值 iK，其中 $K<L$；
• 常数 K，其中 $0 \le K \le 1\,000\,000\,006$。

中间值 iK 按计算顺序编号，从 i1 开始。

最后一行格式必须为：

o J0 J1 ... JN+M

其中第一个字符是小写拉丁字母 o，而 J0,J1,...,JN+M 是若干值。执行完前面所有操作后，它们应当依次等于乘积多项式的系数：

$$c_0,c_1,\ldots,c_{N+M}.$$

输出行中的所有元素，包括运算符、操作数以及最后一行的 o，都用一个空格分隔。

数据范围

• $1 \le N,M \le 100$；
• 算法中的算术操作数量最多为 $200\,000$；
• 多项式 $P(x)$ 与 $Q(x)$ 的系数都是 $0$ 到 $1\,000\,000\,006$ 之间的整数。

评分方式

对于每个测试，你会获得：

$$0.228907\cdot \ln\left(80.1263\cdot \frac{best}{cost}\right)$$

乘以该测试点分值的分数。

其中：

• $best$ 是理论上多项式乘法算法所需非平凡乘法次数的最小值；
• $cost$ 是你输出的算法使用的非平凡乘法次数；
• $\ln$ 是自然对数。

样例

输入

1 1

输出

= a1 + a0
= b1 + b0
= i1 * i2
= a0 * b0
= a1 * b1
= i3 - i4
= i6 - i5
o i4 i7 i5