Bessie의 정원에는 왼쪽에서 오른쪽으로 $1$부터 $N$까지 번호가 붙은 $N$개의 식물이 있다 ($2\leq N\leq 5\cdot 10^5$). Bessie는 식물 $i$에 적어도 $w_i$ ($0\leq w_i \leq 10^6$)단위의 물이 필요하다는 것을 알고 있다. Bessie에게는 $1$부터 $N-1$까지 번호가 붙은 $N-1$개의 수로로 이루어진 매우 특이한 관개 시스템이 있다. 각 수로 $i$에는 단위 비용 $c_i$ ($1\le c_i\le 10^6$)가 연결되어 있다. 따라서 Bessie는 음이 아닌 정수 $k$에 대해 $c_i k$를 지불하고 식물 $i$와 $i+1$에 각각 $k$단위의 물을 공급할 수 있다. Bessie는 바빠서 모든 수로를 사용할 시간이 없을 수도 있다. 각 $2\leq i \leq N$에 대해 처음 $i-1$개의 수로만 사용하여 식물 $1$부터 $i$까지 물을 주는 데 필요한 최소 비용을 구하자.

입력

두 번째 줄에는 공백으로 구분된 $N$개의 정수 $w_1, \ldots, w_N$이 주어진다. 세 번째 줄에는 공백으로 구분된 $N-1$개의 정수 $c_1, \ldots, c_{N-1}$이 주어진다.

세 번째 줄에는 공백으로 구분된 $N-1$개의 정수 $c_1, \ldots, c_{N-1}$이 주어진다.

출력

$N-1$개의 정수를 각각 한 줄에 출력한다. $(i-1)$번째 정수는 처음 $i-1$개의 수로를 사용하여 처음 $i$개의 식물에 물을 주는 최소 비용이어야 한다.

예제

입력 1

3
39 69 33
30 29

출력 1

2070
2127

입력 2

3
33 82 36
19 1

출력 2

1558
676

입력 3

8
35 89 44 1 35 3 62 50
7 86 94 62 63 9 49

출력 3

623
4099
4114
6269
6272
6827
8827

제한

• 입력 4: $N \leq 200$이고, 모든 $w_i \leq 200$이다.
• 입력 5-6: 모든 $w_i \leq 200$이다.
• 입력 7-10: $N \leq 5000$.
• 입력 11-14: 모든 $w_i$와 $c_i$는 서로 독립적으로 균등 무작위 생성된다.
• 입력 15-19: 추가 제한이 없다.