Description

Tommy’s encryption system uses the following string hash algorithm:

int Hash(std::string s, int base, int mod) {
  int result = 0;
  for(int i=0; i<s.length(); i++)
    result = (1ll * result * base + s[i]) % mod;
  return result;
}

Here, $\texttt{base}$ and $\texttt{mod}$ are given parameters, satisfying $257\le\texttt{base}\le\texttt{mod}\le10^9+9$, and $\texttt{mod}$ is a prime number.

Now Dream wants to crack Tommy’s ciphertext. First, Dream needs to find a suitable hash collision. Given $\texttt{base}$, $\texttt{mod}$, and a string $S$, find a string $T$ of the same length such that $|S|=|T|$, $\texttt{hash(S)=hash(T)}$, but $S$ and $T$ differ at least at one position.

If there are multiple valid $T$, output any one of them.

Input Format

The first line contains two positive integers $\texttt{base}$ and $\texttt{mod}$.
The second line contains a string $S$ consisting of lowercase letters.

Output Format

Output one line containing a string $T$ consisting of lowercase letters, representing the answer.

257 997
aabdccbabdcdcadbcabcabaabdbbddbaabcadabcbcdacbbaac

lmzaeccihyailccmzzaxshssgbvjvhthllyofzudraatifnzxy

Hint

Constraints

If $S$ is a string, $|S|$ is its length.

For the first $10\%$ of the testdata, $\texttt{mod}=997$.
For the first $40\%$ of the testdata, $|S|=2\times10^5$ and $S$ is random.
For $100\%$ of the testdata, $50\le|S|\le2\times10^5$, $257\le\texttt{base}<\texttt{mod}\le10^9+9$, and $\texttt{mod}$ is a prime number.

Notes

Minecraft OI Round 4 D
idea & solution: w33z8kqrqk8zzzx33 check: MatKave

Translated by ChatGPT 5