题目内容

给定一个字符串 $s$，请根据其中每个字符出现的频率，对字符串中的字符进行重新排列。

字符的频率是指该字符在字符串 $s$ 中出现的次数。

重新排列后，需要满足：出现频率较高的字符必须排在出现频率较低的字符之前，并且相同字符必须连续放置。

如果多个字符的出现频率相同，则它们之间的顺序可以任意安排。

请输出任意一个满足要求的字符串。

输入描述

输入一行字符串 $s$，表示给定的字符串。

约束

$1 \le |s| \le 5 \times 10^5$

字符串 $s$ 由大小写英文字母和数字组成。

大写字母和小写字母视为不同字符。

输出描述

输出一行字符串，表示按照字符出现频率从高到低重新排列后的结果。

如果多个字符的出现频率相同，则它们之间的顺序任意。

样例1

输入

tree

输出

eert

说明

字符 $e$ 出现 $2$ 次，字符 $r$ 和字符 $t$ 都只出现 $1$ 次。

因此两个字符 $e$ 必须出现在字符 $r$ 和字符 $t$ 之前。

输出 $eert$ 是一种合法结果，$eetr$ 也是合法结果。

样例2

输入

cccaaa

输出

cccaaa

说明

字符 $c$ 和字符 $a$ 都出现了 $3$ 次，因此它们之间的排列顺序任意。

$cccaaa$ 和 $aaaccc$ 都是合法结果。

相同字符必须连续放置，因此 $cacaca$ 不符合要求。

样例3

输入

Aabb

输出

bbAa

说明

字符 $b$ 出现 $2$ 次，字符 $A$ 和字符 $a$ 各出现 $1$ 次。

因此字符 $b$ 应排在字符 $A$ 和字符 $a$ 之前。

需要注意，字符 $A$ 和字符 $a$ 被视为两个不同的字符。