Description:


请计算 \(C_k=\sum_{k\le i\lt n}a_i\times b_{i-k}\) ,并且有 \(n \le 10^5\)\(a\) , \(b\) 中的元素均为小于等于100的非负整数。

Input:


第一行一个整数 \(N\) ,接下来 \(N\) 行,第 \(i+2 ... i+N-1\) 行,每行两个数,依次表示 \(a_i\) , \(b_i \) \((0 \le i \lt N)\)

Output:


输出 \(N\) 行,每行一个整数,第 \(i\) 行输出 \(C_{i-1}\)

Sample Input:


Sample Output:


题解:


\(f_i = a_{n-1}\) ,把i的枚举反序一下,原式变为 \(C_k = \sum f_i\times b_{n-i-k}\)

然后就可以用快速傅里叶变换计算卷积。

代码如下: