zlego

Recent, Bujorel a dat în mintea copiilor şi s-a apucat să se joace cu piese de zlego. El are o piesă formată din N bucăţi numerotate de la 1 la N, fiecare cu o înalţime şi un coeficient de frumuseţe date. Se defineşte un zprefix ca fiind un şir format din una sau mai multe bucăţi consecutive care să înceapă cu piesa 1. Scopul este să aleagă un zprefix, să găsească toate apariţiile acestuia în restul piesei şi să facă suma costurilor de frumuseţe ale acestor apariţii. Pentru o apariţie a zprefixului ales care corespunde secvenţei formate din bucăţile numerotate de la i la j (înălţimea bucăţii 1 este egală cu înălţimea bucăţii i, înălţimea bucăţii 2 este egală cu înălţimea bucăţii i+1 etc.) costul său de frumuseţe este coeficientul de frumuseţe al ultimei bucăţi, adică al lui j.

Bujorel e curios ce se întamplă pentru orice zprefix şi vrea să afişeze suma costurilor de frumuseţe ale tuturor apariţiilor fiecarui zprefix.

Date de intrare

Pe prima linie a fisierului zlego.in se află numarul de teste T. Fiecare test are următorul format: pe prima linie un număr natural N reprezentând dimensiunea piesei de zlego, pe următoarea linie se află N numere întregi, reprezentând înălţimile pieselor, despărţite prin câte un spaţiu, iar pe cea de-a treia linie se află tot N numere întregi, despărţite prin câte un spaţiu, cel de-al i-lea număr reprezentând coeficientul de frumuseţe a celei de-a i-a piese.

Date de ieşire

Fişierul zlego.out trebuie să conţină, pentru fiecare din cele T teste, câte N linii, cea de-a i-a linie reprezentând suma costurilor de frumuseţe ale apariţiilor zprefixului [1,i].

Restricţii şi precizări

• 1 <= N <= 250.000;
• 1 <= T <= 3;
• Inalţimile şi coeficienţii de frumuseţe ale bucăţilor piesei se încadreaza pe 32 de biti cu semn;
• Pentru 20% din teste N <= 100;
• Pentru 50% din teste N <= 1000;
• Atenţie! Bujorel recomandă tipuri de date pe 64 de biţi pentru afişarea rezultatului.

Exemplu

zlego.in

2
3
1 2 1
2 2 2
10
1 1 2 1 1 1 1 2 1 1
1 2 3 4 5 6 7 8 9 10

zlego.out

4
2
2
44
30
11
13
15
6
7
8
9
10

Explicaţie

În cel de-al doilea test, pentru zprefixul [1, 1] obţinem suma costurilor de frumusete ale apariţiilor acestuia 44 = 1+2+4+5+6+7+9+10. Pentru [1, 2] avem 2+5+6+7+10, pentru [1, 3] avem 3+8, pentru [1, 4] avem 4+9, pentru [1, 5] avem 5 + 10, pentru [1, 6] avem 6, pentru [1, 7] avem 7, pentru [1, 8] avem 8, pentru [1, 9] avem 9, iar pentru [1, 10] avem 10.