== include(page="template/taskheader" task_id="zlego") ==

Poveste şi cerinţă...

p<>. 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$.
 
p<>. 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_.

h2. Date de intrare

Fişierul de intrare $zlego.in$ ...

p<>. 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.

h2. Date de ieşire

În fişierul de ieşire $zlego.out$ ...

p<>. 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]$.

h2. Restricţii