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

У једном предузећу за производњу сира налази се N запослених рапоређених у хијерархији тако да сваки запослени осим шефа предузећа (запосленог са редним бројем 1) има тачно једног надређеног.

За сваког запосленог је познат његов допринос предузећу, ai, који представља збир разлика његове компетентности ki и компетентности суседа. Дакле, ai=j(kiksj), где је s низ суседа запосленог i. Два запослена су суседна ако је један од њих надређен оном другом.

Познато је да је компетентност шефа предузећа једнака нули (k1=0), и да компетентности неких запослених могу бити негативне.

Ваш задатак је да на основу хијерархије предузећа и доприноса сваког запосленог одредите компетентност сваког запосленог, или да испишете 1 уколико запосленима није могуће доделити компетентности које задовољавају све услове.

Опис улаза

У првој линији стандардног улаза налази се природан број N - број запослених у предузећу. У наредном реду налази се низ од N бројева ai - допринос сваког од запослених. У следећем реду налази се низ од N1 бројева hi - zапослени hi је надређен zапосленом i+1 и важи hii.

Опис излаза

У једној линији стандардни излаз испишите низ од N бројева ki одвојених размаком - компетентности сваког од запослених, или испишите -1 уколико такав низ не постоји.

Ограничења

Подзадаци

  1. (17 поена) hi=i
  2. (26 поена) hi=(i+1)/2
  3. (23 поена) N2000
  4. (34 поена) Нема додатних ограничења

Примери

Пример 1

Улаз

4
2 -3 1 0
1 2 2

Излаз

0 -2 -1 -2

Објашњење

Запослени (1,2), (2,3), (2,4) су суседни.

a1=k1k2=0(2)=2

a2=k2k1+k2k3+k2k4=20+(2)(1)+(2)(2)=3

a3=k3k2=1(2)=1

a4=k4k2=2(2)=0

Пример 2

Улаз

4
2 -3 1 1
1 2 2

Излаз

-1

Објашњење

Не постоји низ који задовољава све услове.