تحتوي حديقة 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: لا توجد قيود إضافية.