Maximizing String Dissimilarity

Charlie is taking a course named "Fundamentals of Abstract Strings". In this course, the dissimilarity between two strings \(S\) and \(T\) (of equal length \(n\)) is defined as

[ \tilde{\psi}(S,T)=\sum_{i=1}^n\sum_{j=1}^n [i\neq j],[S_i\neq T_j], ]

where \([P]\) is the Iverson bracket which is \(1\) if the proposition \(P\) is true and \(0\) otherwise.

Charlie wonders: For a given lowercase string \(S\), what lowercase string \(T\) (of the same length) maximizes \(\tilde{\psi}(S,T)\)?

Observation: Notice that for any fixed index \(j\) in \(T\), the contribution to \(\tilde{\psi}(S,T)\) is

[ \sum_{\substack{i=1\ i\neq j}}^n [S_i\neq T_j]. ]

This term is maximized when \(T_j\) is chosen such that the number of indices \(i\) with \(S_i\neq T_j\) is as large as possible. Equivalently, if we count the frequency of each letter in \(S\), say \(\mathrm{freq}(c)\) for letter \(c\), then choosing \(T_j = c\) will yield a contribution of

• \(n-\mathrm{freq}(c)\) if \(c = S_j\) (since the count at index \(j\) is excluded),
• \(n-1-\mathrm{freq}(c)\) if \(c \neq S_j\).

A closer look shows that the overall dissimilarity \(\tilde{\psi}(S,T)\) is maximized when the string \(T\) is a constant string, i.e. all characters of \(T\) are the same, and that character \(d\) is chosen to minimize \(\mathrm{freq}(d)\) in \(S\). If there are multiple candidates with the same minimum frequency, choose the lexicographically smallest one.

Task: Given a lowercase string \(S\), output the optimal string \(T\) (of the same length as \(S\)) that maximizes \(\tilde{\psi}(S,T)\) as described above.

inputFormat

The input consists of a single line containing a non-empty string \(S\) of lowercase English letters.

outputFormat

Output a single line containing the optimal string \(T\) that maximizes \(\tilde{\psi}(S,T)\).

sample

abc

ddd