多项式乘法实验室

题目描述

维护当前多项式P，初始P=1。执行q条命令：MUL n c_0…c_n令P乘以给定多项式；COEF e查询系数；DEGREE查询实际次数；VALUE x查询P(x)；PRINT规范输出；RESET令P重新变为1。零多项式次数约定为0。

输入格式

第一行输入正整数q；接下来q行各输入一条上述命令。

数据范围与约定

• $1\le q\le 2\times 10^5$。
• MUL 中 $0\le n\le 2\times 10^5$，输入系数绝对值不超过 $10^9$；COEF 中 $0\le e\le 2\times 10^5$；VALUE 的 $|x|\le 10^9$。
• 任意时刻当前多项式的次数不超过 $2\times 10^5$。
• 将每次 MUL 前后的系数数组长度乘积，以及每次 VALUE、PRINT 扫描的当前系数个数累加，总和不超过 $2\times 10^6$。
• 输入保证每次卷积的乘加结果、当前多项式的所有系数，以及用霍纳法计算 VALUE 时的每一步结果的绝对值均不超过 $9\times 10^{18}$。

输出格式

MUL和RESET不输出；其余命令各输出一行。越界COEF输出0；PRINT遵循L31109的格式，零多项式输出0。

样例

输入

8
MUL 1 1 1
MUL 1 2 1
COEF 1
DEGREE
VALUE 2
PRINT
RESET
PRINT

输出

3
2
12
x^2+3x+2
1