Lab9 Perplexity

Lab9 Perplexity

You cannot submit for this problem because the homework's deadline is due.

Description

It is known that the multiplication of polynomials are just a convolution:
\[f(x)=a_0+a_1x+a_2x^2+\dots,\quad g(x)=b_0+b_1x+b_2x^2+\dots,\]
\[(f*g)(x)=(a_0b_0)+(a_0b_1+a_1b_0)x+(a_0b_2+a_1b_1+a_2b_0)x^2+\dots\]
That is to say, the polynomial coefficient of \(f*g\) is
\[c_n=\sum_{k=0}^na_kb_{n-k}\]
Now given the polynomial coefficient of \(f\) and \(g\) at both \(n\) degrees, find the sum of all the coefficient of \(f*g\).

Format

Name your file as ex2.c

Input

The first line contain only one integer \(n\).
The second and the third lines both contain \(n\) integers, denoting the polynomial coefficient \(a_0\dots a_{n-1}\) and \(b_0\cdots b_{n-1}\).

Output

You should print only one integer, the sum of

Sample

input

4
1 2 3 4
5 6 7 8

output

260

Specification

For all test cases, \(n\leq 10^6, |a_i|,|b_i|\le 10^3\).

Mid2 Sample Exam

Not Claimed
Status
Finished
Problems
3
Open Since
2020-07-10 13:00
DDL
2020-07-12 23:59
Extension
96.0 hour(s)