题目描述

Tommy 的加密系统用了如下的字符串哈希算法：

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;
}

其中 $\texttt{base}$ 和 $\texttt{mod}$ 是给定参数，满足 $257\le\texttt{base}\le\texttt{mod}\le10^9+9$，并且 $\texttt{mod}$ 是一个质数。

现在 Dream 要破解 Tommy 的密文，先需要找到一个适合的哈希碰撞。给定 $\texttt{base}$，$\texttt{mod}$，和一个字符串 $S$，请找一个一样长度的字符串 $T$ 使得 $|S|=|T|$，$\texttt{hash(S)=hash(T)}$，但是 $S$ 和 $T$ 有至少一个位置不同。

如果有多个合法的 $T$，输出任意一个即可。

输入格式

第一行，两个正整数 $\texttt{base}$ 和 $\texttt{mod}$。
第二行，一个由小写字母组成的字符串 $S$。

输出格式

一行，一个由小写字母组成的字符串 $T$，表示答案。

257 997
aabdccbabdcdcadbcabcabaabdbbddbaabcadabcbcdacbbaac

lmzaeccihyailccmzzaxshssgbvjvhthllyofzudraatifnzxy

提示

数据规模与约定

如果 $S$ 是一个字符串，$|S|$ 是它的长度。

对于前 $10\%$ 的数据，$\texttt{mod}=997$。
对于前 $40\%$ 的数据，$|S|=2\times10^5$ 并且 $S$ 随机。
对于 $100\%$ 的数据，$50\le|S|\le2\times10^5$，$257\le\texttt{base}<\texttt{mod}\le10^9+9$，$\texttt{mod}$ 是一个质数。

说明

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