რობოსორტირება

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

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

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

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


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

1.    თუ ახალ სიაში რობოტი ადრინდელია სხვა რობოტზე, მაშინ მისი ძირითადი ნომერი ნაკლებია ან ტოლი სხვა რობოტზე.

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

ტაუ კიტანელებმა გთხოვეს თქვენ დახმარება ამ სიის შედგენაში

 

შესატანი მონაცემები:   პირველი ხაზი შეიცავს n   (≤ ≤ 100000) რობოტების რაოდენობას ქარხანაში, ხოლო მომდევნო ყველა ხაზი არის რობოტების ძირითადი და მეორეხარისხოვანი ნომრები. ნომრები არ აღემატება მილიონს.

გამოსატანი მონაცემები:   დაბეჭდეთ n რაოდენობის ხაზი. ახალი დალაგებული სია.




მაგალითები

შესატანი მონაცემები
10 1 8 8 9 2 10 1 11 4 2 7 2 3 11 2 23 3 3 6 7 დაკოპირება
გამოსატანი მონაცემები
1 8 1 11 2 10 2 23 3 11 3 3 4 2 6 7 7 2 8 9 დაკოპირება