בגינה של Bessie יש $N$ צמחים, הממוספרים מ־$1$ עד $N$ ($2\leq N\leq 5\cdot 10^5$) משמאל לימין. Bessie יודעת שצמח $i$ זקוק ללפחות $w_i$ ($0\leq w_i \leq 10^6$) יחידות מים. ל־Bessie יש מערכת השקיה משונה מאוד ובה $N-1$ תעלות, הממוספרות מ־$1$ עד $N-1$. לכל תעלה $i$ יש עלות ליחידה $c_i$ ($1\le c_i\le 10^6$), כך ש־Bessie יכולה לשלם $c_i k$ כדי לספק לכל אחד מהצמחים $i$ ו־$i+1$ כמות של $k$ יחידות מים, כאשר $k$ הוא מספר שלם לא שלילי. Bessie עסוקה ואולי לא יהיה לה זמן להשתמש בכל התעלות. עבור כל $2\leq i \leq N$, חשבו את העלות המינימלית הנדרשת להשקיית הצמחים $1$ עד $i$ באמצעות $i-1$ התעלות הראשונות בלבד.

קלט

השורה השנייה מכילה $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$ הצמחים הראשונים באמצעות $i-1$ התעלות הראשונות.

דוגמאות

קלט 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: אין מגבלות נוספות.