Sort the three levels

Problem

A task list uses only three priority levels, 0, 1 and 2. Sort the list in one pass without calling sort, using three pointers. Print the sorted list.

Input, output and limits

Input: One line of values, each 0, 1 or 2, separated by spaces.
Output: The sorted list on one line, separated by spaces.
Constraints: 1 ≤ count ≤ 100000
Each value is 0, 1 or 2

Examples

Example

Input

2 0 2 1 1 0

Output

0 0 1 1 2 2

Hints

Try the problem first. Open one hint at a time.

Hint 1

Keep zeros before low, twos after high, and let mid scan the unknown part.

Hint 2

After swapping a 2 to the right do not move mid, because the swapped-in value is not checked yet.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

Closest pair of costsmedium
Triplets that cancel outmedium
Pairs under a limitmedium
At most two copiesmedium
Container with the most watermedium

All Python problems

Problem

Input, output and limits

Examples

Hints

More Two Pointers problems

Problem

Input, output and limits

Examples

Hints

More Two Pointers problems