ბუშტები

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

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

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

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

წყარო: CEOI, 2011, #1


                ორგანიზატორები გეგმავენ n ცალი ბუშტით ჩაატარონ წვეულება. ბუშტები წრიული ფორმისაა და განთავსებულია იატაკზე (წრფეზე).

                ბუშტები თავიდან არაა გაბერილი, შესაბამისად მათი რადიუსი ნულის ტოლია. მე-k-ე ბუშტი დამაგრებულია x[k] კოორდინატზე. ისინი უნდა გავბეროთ რიგ-რიგობით, მარცხნიდან მარჯვნივ. ბუშტი ნელ-ნელა იბერება იქამდე, სანამ ის მიაღწევს თავის ზედა ზღვარს - r[k]-ს, ან შეეხება სხვა უკვე გაბერილ ბუშტს.

                ორგანიზატორებს აინტერესებთ რა მოცულობის ჰაერი დასჭირდებათ მათ ყველა ბუშტის გასაბერად. თქვენ უნდა იპოვოთ თითოეული ბუშტისთვის მისი საბოლოო რადიუსი.

                ინფუთის პირველი ხაზი შეიცავს n-ს (1 <= n <= 200000). შემდეგი n ხაზი აღწერს ბუშტებს: მე-k-ე მათგანი შეიცავს ორ რიცხვს: x[k] (0 <= x[k] <= 1000000000) და r[k] (1 <= r[k] <= 1000000000). შეგიძლიათ ჩათვალოთ რომ ბუშტების კოორდინატები ზრდადობითაა (მკაცრად) დალაგებული.

                აუთფუთში უნდა გამოიტანოთ ზუსტად n ცალი ხაზი. მე-k-ე ხაზი უნდა აღნიშნავდეს თუ რა რადიუსამდე გაიბერება მე-k-ე ბუშტი. თქვენი პასუხი (თითოეული ბუშტის შემთხვევაში) ჩაითვლება სწორად მაშინ, თუ ის განსხვავდება ნამდვილი პასუხისგან მაქსიმუმ 0.001-ით.




მაგალითები

შესატანი მონაცემები
3 0 9 8 1 13 7 დაკოპირება
გამოსატანი მონაცემები
9.000 1.000 4.694 დაკოპირება