Lyndonization

题目描述

You are given a string $s$ of length $n$ consisting of lowercase English letters.

You may perform modifications: each modification replaces one position of the string with an arbitrary lowercase English letter. You must, using at most $2\lceil\sqrt{n}\rceil + 5$ modifications, turn $s$ into a Lyndon word.

A non-empty string $w$ is a Lyndon word if it is strictly smaller (lexicographically) than every one of its proper suffixes. For example, $\texttt{aab}$ is a Lyndon word: its proper suffixes are $\texttt{ab}$ and $\texttt{b}$, and $\texttt{aab}$ is smaller than both. On the other hand, $\texttt{aba}$ is not: its proper suffix $\texttt{a}$ is smaller than $\texttt{aba}$.

It can be proven that such a set of modifications always exists. You only have to output any resulting string that satisfies the constraints.

输入格式

The first line contains one integer $n$ $(1 \le n \le 10^6)$.

The second line contains a string $s$ of length $n$ consisting of lowercase English letters.

输出格式

Output one line containing a string $t$ of length $n$ consisting of lowercase English letters, such that:

• $t$ is a Lyndon word;
• $t$ differs from $s$ in at most $2\lceil\sqrt{n}\rceil + 5$ positions.

If several answers are possible, output any of them.

样例输入 #1

5
liang

样例输出 #1

ailng

样例输入 #2

8
rifleman

样例输出 #2

iillmmnn