Foes from the Future


Submit solution

Points: 1
Time limit: 1.0s
Java 3.0s
Python 3.0s
Memory limit: 640M

Authors:
Problem type
Allowed languages
Assembly, C, C++, Java, Kotlin, Pascal, Perl, Python, Scratch, Text

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 z somewhere

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

There are no comments at the moment.