Get Min Cost Data

Fill every ? with a lowercase letter. The cost of each position is the number of times the same letter appears before it. First minimize the total cost, then make the whole result lexicographically smallest.

输入格式

One line containing data. The original bounds are 1≤length≤100000, with at least one ?, and every other character in a..z.

输出格式

Output the complete filled-in lowercase string.

样例 1

输入：

aaaa?aaaa

输出：

aaaabaaaa

样例 2

输入：

abcd?

输出：

abcde

样例 3

输入：

?a?cdefghijklmnopqrstuvwxyz

输出：

aabcdefghijklmnopqrstuvwxyz

样例说明

The outputs are aaaabaaaa, abcde and aabcdefghijklmnopqrstuvwxyz. In the third example you cannot fill the letters directly in the order the min-heap picks them; the chosen a and b must be sorted into the question-mark positions.