多个公式积木连续展开

题目描述

给定n个公式积木：1 a表示(x+a)²，2 a表示(x-a)²，3 a表示(x+a)(x-a)。先分别展开，再按输入顺序将全部二次多项式相乘。

输入格式

第一行输入正整数n；接下来n行各输入类型type和整数a，type为1、2或3。

数据范围与约定

• $1\le n\le 1000$，$|a|\le 10^9$。
• 输入保证每次展开、相乘、同次项累加得到的所有中间系数和最终系数均在 signed 64-bit 整数范围内。
• 最终需要输出全部 $2n+1$ 个系数，因此输出规模为 $O(n)$；顺次乘入二次式的总计算量为 $O(n^2)$。

输出格式

第一行输出最终次数2n；第二行输出从常数项到x^(2n)项的2n+1个系数，0系数也保留。

样例

输入

2
1 1
3 2

输出

4
-4 -8 -3 2 1