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