Insertion Sort Implementation

Ashcombe Clinic keeps one tray of patient cards, ordered by appointment number. The cards come off the printer in whatever order they were requested, so the receptionist takes the next card, walks back through the cards already in the tray, and slides it into the right gap. The rota screen has to show the finished tray, and it has to be produced by that same slide-it-into-place routine rather than by Python's built-in ordering.

Task: Print the appointment numbers in ascending order, arranging them with an insertion sort you write yourself.

Input

A single line holding 1 to 1000 integers separated by single spaces. Numbers may repeat and may be negative.

Output

One line holding every value in ascending order, separated by single spaces. Every value that came in must come out, repeats included.

Example:

Input:
5 2 8 1 9

Output:
1 2 5 8 9