Description

请计算

\[C[k]=\sum_{k\le i<n}(a[i]*b[i-k])\] 。

有 \(n < = 10^5\)，a,b中的元素均为小于等于100的非负整数。

Input

第一行一个整数\(N\),接下来\(N\)行，第\(i+2..i+N-1\)行，每行两个数，依次表示\(a[i],b[i]\) (\(0 \le i < N\))。

Output

输出\(N\)行，每行一个整数，第\(i\)行输出\(C[i-1]\)。

Sample Input

5
3 1
2 4
1 1
2 4
1 4

Sample Output

24
12
10
6
1

Source

BZOJ