多重哈希攻击

本题是题目《哈希攻击》的困难版本。

题目描述

在 $\mathcal{HASH HACKER}$ 的攻击下，Gino 自认为没有破绽的字符串哈希被攻破了！可是 Gino 并不打算放弃。于是，他找到了一种叫「多重哈希」的技术。

我们知道，字符串可以通过以下方式映射到一个整数上：

$$ f(s) = ( \sum_{i=1}^{n} a_i \times b^{n-i} )\bmod p $$

其中，$a_i$ 是字符串第 $i$ 位对应字符所需要映射的值，$b$ 是小于 $p$ 的正整数，$p$ 是一个大质数。

而「多重哈希」，会使用两组及以上的 $b,p$ 将字符串同时映射到两个及以上的整数上，以大大降低哈希冲突的概率。

Gino 使用的哈希函数与之前一样：

int strhash(char s[], int len, int b, int p)
{
    int val = 0;
    for (int i = 0; i < len; i++)
    {
        val = (1ll * val * b + s[i] - 'a' + 1) % p;
    }
    return val;
}

不同的是，他这次决定使用两组不相同的 $b,p$ 进行哈希。

请你找到任意两个字符串，使它们满足以下条件：

• 仅由小写字母 a-z 组成
• 两者长度相同，且长度 $n$ 满足 $1 \le n \le 10^4$
• 两者不完全相同，却在给定的两组 $b,p$ 的条件下都有着一致的哈希值

输入

共两行，每行两个由空格隔开的正整数 $b,p$，含义与题意相同。

• 对于 $30 \%$ 的数据，$31\le b \lt p \le 33331$
• 对于 $100 \%$ 的数据，$31\le b \lt p \le 1000000007$

所有数据均保证 $p$ 是一个质数。

所有数据均保证 $b_1\not ={b_2}$ 与 $p_1\not ={p_2}$ 至少有一个成立

输出

两行，分别输出你找到的两个字符串，需要满足题目给出的条件。满足条件的字符串有很多组，你只需要输出任意一组即可。

输入样例

31 1009
114 1033

输出样例（答案不唯一）

rkfmftoxsjtoxsjrkfmfrkfmftoxsjrkfmfrkfmfrkfmftoxsj
toxsjtoxsjtoxsjtoxsjrkfmftoxsjrkfmftoxsjrkfmfrkfmf

样例解释

$b=31,p=1009$ 的情况下，两字符串的哈希值都为 $0$。

$b=114,p=1033$ 的情况下，两字符串的哈希值都为 $1$。

Hint

为了降低思考难度，本题的输出样例极其富有启发性。

对于随机数生成函数 rand 来说，请注意，它的随机性有可能在你的本地运行环境下的表现并不好。

在出题者的本地环境下，RAND_MAX: $32767$，即 $2^{15} - 1$

• 二进制表示下，生成的随机数的最低位的循环节：$2^{17}$
• 二进制表示下，生成的随机数的次低位的循环节：$2^{18}$
• 二进制表示下，生成的随机数的第三低位的循环节：$2^{19}$

也许可以解答你在本地调试时遇到的 “灵异事件”。

---

$\mathcal{HASH HACKER}:$