Foes from the Future
Ed Small, an algorithms teacher at RMIT, is often considered a founder of RMIT MATRIX. Unfortunately, Fionn's reckless use of time travel (in B: Back to the Funk) has put this student club in jeopardy.
By travelling to the past, Fionn has created an alternate timeline. In this new branch of time, an evil, alternate version of Ed Small known as Edward Large has discovered the secrets of competitive programming and time travel from Fionn's laptop.
Armed with inspiration and knowledge, Edward Large proceeded to form his own competitive programming club - RMIT TENSOR - and trained them ruthlessly for decades, refusing to let the students graduate. Then, he used time travel to cross timelines, transporting his team to the present day in our timeline.
With RMIT TENSOR behind him, Edward Large approaches RMIT MATRIX with an evil ultimatum: the two clubs will compete, and if MATRIX loses, Edward Large will alter our timeline so that Ed Small never became a teacher in the first place; not only will RMIT MATRIX never exist, but the Algorithms and Analysis cohort will be doomed to fail without Ed's brilliant teaching skills.
MATRIX stands no chance against TENSOR in a competition. Fortunately, Ed has a plan to sabotage the game.
TENSOR uses a unique programming language called Z. Lines in Z consist only of lowercase English letters. A line in Z compiles if it meets all of the following criteria:
- The line is a palindrome
- The line contains the letter
zsomewhere
When TENSOR produces an algorithm in Z, they print each line onto a punch card. Normally, Edward Large gives these punch cards to the judges for evaluation.
That is precisely where Ed's plan comes in. Before the competition, Ed Small will trap Edward Large in a computer simulation, making him believe he is really at the competition. Then, during the competition, Ed Small will pretend to be Edward Large, acting all evil and sinister. When TENSOR gives him a punch card, he may secretly tamper with it:
- If the line compiles, he will overwrite as few letters as possible to create a new, distinct line that still compiles
- If the line does not compile, he will not change it
If done this way, Edward Large and TENSOR will have no clue that they have been played. There will be no unexpected compilation failures, but their programs will not work correctly.
How should Ed go about this?
Input
The input consists of two lines. The first line contains an integer \(3 \leq n \leq 80\). The second line contains a string \(w\) of length \(n\) (\(|w| = n\)), consisting of the lowercase English characters \(a, b, c, \ldots , x, y, z\).
Output
If \(w\) compiles, output a new string \(w_a\):
- \(w_a\) must be distinct from \(w\)
- \(w_a\) must compile
- \(w_a\) must be the same length as \(w\)
- \(w_a\) must differ from \(w\) by as few characters as possible
If there are multiple solutions, output any of them.
If \(w\) does not compile, output \(w\) unchanged.
Examples
Example 1
Input:
5
bzczb
In this example, \(w\) compiles.
Output:
bzxzb
This is one of many outputs that satisfies this question.
Example 2
Input:
6
zbcdxz
In this example, \(w\) does not compile.
Output:
zbcdxz
Example 3
Input:
4
zaaz
Output:
zbbz
This is one of many outputs that satisfies this question.
Example 4
Input:
5
aacaa
Output:
aacaa
Comments