ჭიანჭველები და ჭიამაია

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

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

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

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

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


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

·         ხის ნებისმიერი ადგილიდან შეიძლება მიღწევა ხის სხვა ადგილამდე (ფოთლამდე ან განშტოებამდე) ზუსტად ერთი გზით; ყველა ჭიანჭველა სწორედ ამ გზას ირჩევს ჭიამაიამდე მისაღწევად.

·         თუ ჭიანჭველა უკვე არის იმ ადგილას, სადაც ჭიამაია დაფრინდება ჭიამაია მაშინვე მიდის.

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

·         თუ ორი ჭიანჭველა ერთდროულად მიადგება განშტოებას, მოძრაობას აგრძელებს ის ჭიანჭველა, რომლის ნომერიც ნაკლებია.

·         როცა ჭიანჭველა მივა ჭიამაიასთან, ჭიამაია მიფრინავს და მის ადგილს ჭიანჭველა იკავებს.

ჭიამაია ჯიუტია და ხეზე რამდენჯერმე დაფრინდება. ყოველ ჯერზე ჭიანჭველები თავიდან იწყებენ მოძრაობას, რომ გააგდონ დაუპატიჟებელი სტუმარი.

სიმარტივისთვის შეგვიძლია ჩავთვალოთ, რომ ყოველი ტოტის გავლას ნებისმიერი ჭიანჭველა დროის ერთეულს ანდომებს.

 

დაწერეთ პროგრამა, რომელიც:

·         წაიკითხავს ხის აღწერილობას, ჭიანჭველების საწყის ადგილმდებარეობასა და ჭიამაიას დაფრენის ადგილებს მიმდევრობით.

·         ყოველი ჭიანჭველისთვის იპოვის საბოლოო პოზიციას და რაოდენობას, თუ რამდენჯერ გააგდო კონკრეტულმა ჭიანჭველამ ჭიამაია.

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

პირველ ხაზზე შემოდის n, განშტოებებისა და ფოთლების რაოდენობა ხეში 1 ≤ n ≤ 5000. ვთვლით, რომ ფოთლები და განშტოებები გადანომრილია 1-დან n-ის ჩათვლით. შემდეგ n-1 ხაზში, აღწერილია ტოტები. შემოდის ორი რიცხვი a და b, რაც ნიშნავს, რომ ეს ტოტი ერთმანეთთან აკავშირებს a და b -ს. ტოტების მეშვეობით შესაძლებელია ერთი ადგილიდან მეორეში გადასვლა. (n+1) ხაზში შემოდის რიცხვი k, 1 ≤ k ≤ 1000 და k ≤ n. k ჭიანჭველების რაოდენობაა, რომლებიც ხეს იცავენ. შემდეგ k ხაზში შემოდის ერთი დადებითი რიცხვი არაუმეტეს n-ისა.  რიცხვი, რომელიც წერია (n + 1 + i) ხაზში აღნიშნავს i-ური ჭიანჭველის საწყის ადგილსამყოფელს. არცერთ ფოთოლსა და განშტოებაზე არ ზის ერთზე მეტი ჭიანჭველა. (n + k + 2) ხაზში შემოდის რიცხვი L, 1≤L≤500. L აღნიშნავს, თუ რამდენჯერ დაფრინდა ხეზე ჭიამაია. შემდეგ L ხაზში შემოდის დადებითი რიცხვი არაუმეტეს n-ისა ადგილი, სადაც წარმატებულად დაფრინდება ჭიამაია.

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

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




მაგალითები

შესატანი მონაცემები
4 1 2 1 3 2 4 2 1 2 2 2 4 დაკოპირება
გამოსატანი მონაცემები
1 0 4 2 დაკოპირება