T533480 「GFOI Round 2」Abstract String Basic (English ver.)

**[Chinese statement](https://www.luogu.com.cn/problem/P11279). You must submit your code at the Chinese version of the statement.**

Charlie is taking a course called *Basics of Abstract Strings*. > **Definition 3.1:** For two lowercase strings $S$ and $T$ of the same length, their **similarity** is defined as the number of matching characters in corresponding positions. Formally, if $|S| = |T| = n$, then the similarity between $S$ and $T$ is given by $\psi(S, T) = \sum\limits_{i=1}^n \sum\limits_{j=1}^n [i = j][S_i = T_j]$. > > **Lemma 3.1:** For any lowercase string $S$, there exists a unique lowercase string $T$ that maximizes $\psi(S, T)$. > > **Proof of Lemma 3.1:** ... Charlie’s mind begins to wander, and he starts scribbling aimlessly on his paper. Suddenly, he comes up with a new idea: what if he defines the **dissimilarity** between $S$ and $T$ as the number of pairs where both the position and the character are different? Formally, this similarity can be defined as $\tilde{\psi}(S, T) = \sum\limits_{i=1}^n \sum\limits_{j=1}^n [i \neq j][S_i \neq T_j]$. This whimsical definition snaps Charlie out of his daydream. Now, he wonders: what kind of lowercase string $T$ would maximize the dissimilarity between $S$ and $T$? **Note:** The square brackets $[x]$ represent Iverson brackets, which evaluate to $1$ if the condition $x$ is true, and $0$ otherwise.

无

无

#### Sample $1$ Explanation When $T = \texttt{godfather}$, $\tilde{\psi}(S, T) = 72$, reaching the maximum value. Note that there may be more than one valid answer. #### Subtasks and Constraints | Subtask ID |$n\le$ | Special Properties | Score | | :-----------: | :-----------: |:----:|:----:| |$0$ |$28$ | Tests are samples | $0$ | |$1$ |$4$ | No |$20$ | |$2$ |$10^6$ | $S$ doesn't contain the character `z` |$20$ | |$3$ |$10^3$ | No |$20$ | |$4$ |$10^6$ | No |$40$ | For all tests, it is guaranteed that: - $1 \le n \le 10^6$; - $S$ consists only of lowercase letters.