You are given a string s of lowercase English letters.

Rearrange it as follows:

1. List the distinct characters of s in the order of their first occurrence.
2. Emit rounds: in each round, go through that list in order and output one occurrence of every character that still has copies remaining.
3. Repeat until all characters are used.

Return the resulting string.

Examples

Example 1

Input: s = "cccabbbbcca"
Output: "cabcabcbcbc"
Explanation: First-occurrence order is c, a, b with counts c×5, a×2, b×4.
Rounds: "cab", "cab" (a is used up), "cb", "cb" (b is used up), "c".
Concatenated: "cabcabcbcbc".

Example 2

Input: s = "zzz"
Output: "zzz"
Explanation: One distinct character; every round emits a single z.