ხელფასები

დროის ლიმიტი: 5 წმ

მეხსიერების ლიმიტი: 256 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: პოლონეთი, ოლიმპიადა 19, ეტაპი 3


ბაიტლენდის პროგრამული უზრუნველყოფის კორპორაციაში (ბპუკ) დასაქმებულია  თანამშრომელი. ბპუკ-ის მკაცრი იერარქიის გამო, თითოეულ მათგანს ჰყავს უშუალო ხელმძღვანელი, თუმცა ეს არ ეხება ფაბრიკის დირექტორის, რომელიც ყველა დანარჩენი თანამშრომელის ხელმძღვანელია (იქნება ეს უშუალო თუ არაპირდაპირი გზებით). ყველა თანამშრომელს აქვს უნიკალური თვიური ხელფასი 1-დან  ბაიტდოლარამდე (ჩათვლით) დიაპაზონში. თითოეული ხელმძღვანელი გამოიმუშავებს მეტს ვიდრე მისი ნებისმიერი ხელქვეითი.

 ბაიტლენდის კანონის მიხედვით, ზოგიერთი პოზიციის თანამშრომლების ხელფასები შეიძლება იყოს საჯარო. ასევე, თუ თანამშრომლის ხელფასი საჯაროდაა ცნობილი, მაშინ მისი ხელმძღვანელის ხელფასიც საჯაროდ უნდა იყოს ცნობილი.

 ბაიტლენდის შემოსავლებისა ანტი-კორუფციის სამსახურმა (ბშას) გადაწყვიტა პროგრამული ბპუკ-ის შემოწმება. იმისათვის, რომ ბშას უსაფუძვლოდ არ შეიჭრას ბპუკ-ში, მათ სურთ გაიგონ ყველა იმ თანამშრომლის ხელფასი, რომლებიც საჯაროდ არაა ცნობილი, მაგრამ შეიძლება განისაზღვროს სხვა თანამშრომლების საჯაროდ ცნობილი ხელფასების მიხედვით.

შესატანი მონაცემები:

 შესატანი მონაცემების პირველ ხაზი შეიცავს ერთ მთელ რიცხვ n-ს (1<=n<=1000000)

რომელიც აღნიშნავს ბპუკ-ის თანამშრომლების რაოდენობას. თანამშრომლები გადანომრილები არიან 1-დან n-მდე.

 შემდეგი  ხაზი შეიცავს ინფორმაციას თანამშრომლების შესახებ. რიგით (i+1)-ე ხაზი აღწერს i-ური ნომრის მქონე თანამშრომელს ორი, სფეისით გამოყოფილი რიცხვის pi და zi საშუალებით (1<=pi<=n, 0<=zi<=n) .  აღნიშნავს -ური ნომრის მქონე თანამშრომლის უშუალო ხელმძღვანელის ნომერს. თუ pi=i, ანუ ეს თანამშრომელი თვითონ ბპუკ-ის დირექტორია. თუ zi>0 მაშინ ის აღნიშნავს i-ური ნომრის მქონე თანამშრომლის ხელფასს. ხოლო, თუ zi=0, მაშინ ამ თანამშრომლის ხელფასი უცნობია. გარანტირებულია, რომ  zi-ის არანულოვანი მნიშვნელობები წყვილ-წყვილად განსხვავებულია.

შემომავალი მონაცემები ყოველთვის ისე იქნება შედგენილი, რომ აუცილებლად იარსებებს მინიმუმ ერთი გზა, რომლის მიხედვითაც, შესაძლებელი იქნება იერარქიის წესის დარღვევის გარეშე თანამშრომლებისათვის ხელფასების მინიჭება.

 მთლიანი ქულების 54%-თვის მოქმედებს დამატებითი შეზღუდვა n<=10000.

 გამოსატანი მონაცემები:

 

თქვენმა პროგრამამ უნდა გამოიტანოს n ცალი ხაზი, რომელთაგან თითოეული შეიცავს ერთ მთელ რიცხვს. თუ i-ური ნომრის მქონე თანამშრომლის ხელფასი საჯაროა ან შეგვიძლია გამოვთვალოთ დანარჩენების ცნობილი ხელფასების საშუალებით, მაშინ გამოსატანი მონაცემების i-ური ხაზი უნდა იყოს i-ური ნომრის მქონე თანამშრომლის ხელფასი. სხვა შემთხვევაში i-ურ ხაზზე უნდა გამოიტანოთ 0.

 




მაგალითები

შესატანი მონაცემები
10 2 2 2 10 1 0 2 9 2 5 4 0 6 0 6 0 5 0 5 0 დაკოპირება
გამოსატანი მონაცემები
2 10 1 9 5 8 0 0 0 0 დაკოპირება

შენიშვნა

მე-3 თანამშრომელი უნდა გამოიმუშავებდეს 1 ბაიტდოლარს, ხოლო მე-6 თანამშრომელს უნდა ჰქონდეს 8 ბაიტდოლარის ოდენობის ხელფასი. მე-7, მე-8, მე-9 და მე-10 თანამშრომლების ხელფასები კი ცალსახად არ განისაზღვრება ცნობილი ხელფასების მიხედვით.