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

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

За сваког запосленог је познат његов допринос предузећу, \(a_{i}\), који представља збир разлика његове компетентности \(k_{i}\) и компетентности суседа. Дакле, \(a_{i}=\sum_{j}(k_{i}-k_{s_{j}})\), где је \(s\) низ суседа запосленог \(i\). Два запослена су суседна ако је један од њих надређен оном другом.

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

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

Опис улаза

У првој линији стандардног улаза налази се природан број \(N\) - број запослених у предузећу. У наредном реду налази се низ од \(N\) бројева \(a_{i}\) - допринос сваког од запослених. У следећем реду налази се низ од \(N-1\) бројева \(h_{i}\) - zапослени \(h_{i}\) је надређен zапосленом \(i+1\) и важи \(h_{i}\leq i\).

Опис излаза

У једној линији стандардни излаз испишите низ од \(N\) бројева \(k_{i}\) одвојених размаком - компетентности сваког од запослених, или испишите -1 уколико такав низ не постоји.

Ограничења

Подзадаци

  1. (17 поена) \(h_{i}=i\)
  2. (26 поена) \(h_{i}=(i+1)/2\)
  3. (23 поена) \(N\leq 2000\)
  4. (34 поена) Нема додатних ограничења

Примери

Пример 1

Улаз

4
2 -3 1 0
1 2 2

Излаз

0 -2 -1 -2

Објашњење

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

\(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

Улаз

4
2 -3 1 1
1 2 2

Излаз

-1

Објашњење

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