Напомена: ово је незванична копија задатака. Као таква, не гарантује се да ће овај сајт бити одржаван, и немојте се изненадити ако са њега задаци одједном нестану.

Egy sajtgyárban \(N\) foglakoztatott dolgozik, akik hierarchikus viszonyban állnak egymással. Mindegyik foglalkoztatottnak a vállalat főnökén (az 1 sorszámú foglalkoztatotton) kívül pontosan egy felettese van.

Minden foglalkoztatottra ismert az \(a_{i}\) érték, a hozzájárulása a céghez, amely egyenlő a saját alkalmassága, \(k_{i}\) , és szomszédai alkalmassága közötti különbségek összegével. Vagyis \(a_{i}=\sum_{j}(k_{i}-k_{s_{j}})\), ahol \(s\) az \(i\) - edik foglalkoztatott szomszédainak sorozata. Két foglalkoztatott akkor szomszédos, ha egyikük felettese a másiknak.

Azt tudjuk, hogy a főnök alkalmassága egyenlő nullával (\(k_{1}=0\)), és egyes beosztottak alkalmassága negatív szám is lehet.

Feladatotok az, hogy a vállalatban fennálló hierarchia és a foglalkoztatottak hozzájárulása alapján meghatározzátok minden foglalkoztatott alkalmasságát, vagy, hogy kiírassatok -1-et, ha nem lehetséges kiosztani úgy az alkalmasságokat, hogy azok minden feltételt kielégítsenek.

Bemenet

A szabványos bemenet első sorában beviszünk egy \(N\) természetes számot, a foglalkoztatottak számát. A következő sorban egy sorozat áll \(N-1\) számmal, a \(h_{i}\) értékekkel. A \(h_{i}\) foglalkoztatott felettese az \(i+1\) foglalkoztatottnak, és érvényes, hogy \(h_{i}\leq i\). A következő sorban az \(a_{i}\) számok \(N\) elemű sorozata található, a foglalkoztattak hozzájárulása egyenként.

Kimenet

A szabványos kimenet egy sorában kiíratni a \(k_{i}\) számok (a foglalkoztatottak alkalmasságának) \(N\) elemű sorozatát szóközökkel elválasztva, vagy kiíratni -1-et, ha ilyen sorozat nem létezik!

Korlátozások

Alfeladatok

  1. (17 pont) \(h_{i}=i\)

  2. (26 pont) \(h_{i}=(i+1)/2\)

  3. (23 pont) \(N\leq 2000\)

  4. (34 pont) Nincsenek további korlátozások

Példák

1. példa

Bemenet

4
2 -3 1 0
1 2 2

Kimenet

0 -2 -1 -2

Magyarázat

Az (1,2), (2,3), (2,4) foglalkoztatottak szomszédok.

\(a_{1}=k_{1}-k_{2}=0-(-2)=2\)

\(a_{2}=k_{2}-k_{1}+k_{2}-k_{3}+k_{2}-k_{4}=-2-0+(-2)-(-1)+(-2)-(-2)=-3\)

\(a_{3}=k_{3}-k_{2}=-1-(-2)=1\)

\(a_{4}=k_{4}-k_{2}=-2-(-2)=0\)

2. példa

Bemenet

4
2 -3 1 1
1 2 2

Kimenet

-1

Magyarázat

Nincs olyan sorozat, amely kielégíti az összes feltételt.