At the School of Magic and Witchcraft of Brutewarts, there is a library containing millennia-old magical knowledge. In the library, there are several bookshelves, each dedicated to a different book category. The librarian, Karina McGonagall, is very meticulous about the indexing of books on the shelves, and her favorite category is the one about the Three Little Pigs.

In a given category, she likes to keep the books sorted by their titles in lexicographic order—that is, the same order as they would appear in a dictionary. For instance, the word "abacate" comes before "abacaxi" in the dictionary, since when we look at the first position where they differ, the letter "t" comes before the letter "x" in the alphabet.

After a lot of effort, Karina finally finished organizing her most ambitious bookshelf: the shelf of all finite strings containing letters from "a" to "z". Although there are some books with repeated titles, books titled with every imaginable finite string are already there, perfectly sorted lexicographically.

On this shelf, she noticed that magic students almost always read one of the first books, located near the beginning, and it was rare for anyone to want to reach the end.

Karina's favorite book title is $$$S$$$, and she would like to reposition it in a place where it will be more frequently read. Since she cannot change the ordering, she only wants to slightly modify the title so that, when reinserted in its correct position, it will be as close to the beginning as possible. To avoid harming comprehension, she will make the following change at most once:

• Choose two positions $$$i, j$$$ $$$(1 \leq i, j \leq N)$$$ and swap the characters $$$S_i$$$ and $$$S_j$$$, that is, $$$S_i$$$ goes to position $$$j$$$ and vice versa.

As she is already very tired after grading Transfiguration exams, the poor librarian asks for your help.

Given the title of the book, what should its new title be in order to meet Karina's request?