Under construction

Still being built. Things may change

Sorting Crayons

Time limit8sMemory limit1024 MB

Summary
Given strings of crayon types, the task is to sort each string so lowercase letters come first, then uppercase, then digits, each in ascending order.
Level

Easy1 of 10

Topics
Sorting, Implementation
Solved
No attempts yet

Problem

Yokohama-kun has crayons in a case. Each crayon type is a single character: a lowercase English letter, an uppercase English letter, or a digit. The case may contain several crayons of the same type.

One day he lent the case to his family, and the crayons came back in a mixed order. Yokohama-kun likes neat arrangements, so he decided to reorder them in the following way.

  • Lowercase letters are placed to the left of all uppercase letters, and uppercase letters are placed to the left of all digits.
  • Among lowercase letters, the one earlier in alphabetical order is placed further left.
  • Among uppercase letters, the one earlier in alphabetical order is placed further left.
  • Among digits, the smaller digit is placed further left.

Find the order of the crayons after sorting.

Input

The input consists of multiple datasets. Each dataset is given in the following format.

SS

Each dataset is one line containing a string SS that represents the order of the crayons. The ii-th character of SS from the left is the type of the crayon at position ii from the left.

The length of SS is between 1 and 1,000, inclusive, and SS consists of lowercase English letters, uppercase English letters, and digits.

The end of the input is marked by a line containing only #. There are at most 50 datasets.

Output

For each dataset, output on one line the string that represents the order of the crayons after sorting.

Examples1

  1. Example 1

    Input
    ICPC2023YokohamaRegional
ICPCJapaneseAlumniGroup
GoodLuckForAllContestants
#
    Expected output
    aaaeghiklmnoooCCIPRY0223
aaeeilmnnopprsuuACCGIJP
acdekllnnoooorsstttuACFGL