Challenge: Sort the Marks

Lab Python Beginner 10 points

Read exam marks (whole numbers from 0 to 100) and print them sorted using counting sort. Then print the most common mark (if there's a tie, the smallest such mark).

Input

One line of marks.

Output

Line 1: the sorted marks. Line 2: Most common: <mark>

Example

Input

70 35 90 70 100 35 70

Output

35 35 70 70 70 90 100
Most common: 70

Sample input available Sample output available

Editor

Python

Hints

Make a list of 101 zeros and add 1 at each mark.

Walk the counts from 0 to 100 to write the marks in order.

Solution explanation

O(n + 101) time – and the counts give you the most common mark for free.

Show solution

marks = list(map(int, input().split()))
count = [0] * 101
for m in marks:
    count[m] += 1
out = []
for v in range(101):
    out.extend([v] * count[v])
print(" ".join(map(str, out)))
best = 0
for v in range(101):
    if count[v] > count[best]:
        best = v
print("Most common:", best)

Output

Answer