现在海蒂已经准备好破解科瓦里安夫人的哈希函数了。
Kovarian 夫人对于姓名变更有一套非常严格的规则。仅当对两个名称使用以下哈希函数导致冲突时才可以互换。然而,散列函数是参数化的,因此人们总能找到一组导致此类冲突的参数。海蒂决定利用这一点为自己谋利。
给定两个字符串$$$w_1$$$、$$$w_2$$$,长度相等$$$n$$$,由小写英文字母和整数$$$m$$$组成。
考虑标准多项式哈希函数:
$$$H_p(w) := \left( \sum_{i=0}^{|w|-1} w_i r^i \right) \mbox{mod}(p)$$$
其中 $$$p$$$ 是某个素数,$$$r$$$ 是某个数字,例如 $$$2\leq r \leq p-2$$$。
目标是找到 $$$r$$$ 和素数 $$$p$$$ ($$$m \leq p \leq 10^9$$$) 使得 $$$H_p(w_1) = H_p(w_2)$$$。
字符串 $$$w_1$$$ 和 $$$w_2$$$ 是从长度为 $$$n$$$ 的小写英文字母的所有字符串中独立随机采样的。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$10 \le n \le 10^5$$$, $$$2 \le m \le 10^5$$$)。
第二行和第三行分别包含单词 $$$w_1$$$、$$$w_2$$$,它们是从所有长度为 $$$n$$$ 的小写英文字母字符串中独立随机采样的。
输出
输出整数$$$p,r$$$。
$$$p$$$ 应该是 $$$[m, 10^9]$$$ 范围内的质数,$$$r$$$ 应该是满足 [2,p-2]$$$ 中 $$$r\ 的整数。
保证至少存在一个解决方案。如果存在多个解决方案,请打印其中任何一个。
示例
输入 #1
10 5 bgcbaaaaaa cccaaaaaaa
输出 #1
5 2
输入 #2
10 100 melodypond riversongg
输出 #2
118219 79724
注意
在第一个示例中,请注意,即使 $$$p=3$$$ 和 $$$r=2$$$ 也会导致哈希冲突,但这不是正确的解决方案,因为 $$$m$$$ 是 $$$5$$$,因此我们需要 $$$p\geq 5$$$。
在第二个示例中,我们注意到末尾有额外的“g”。我们只是没有意识到“River Song”和“Melody Pond”的长度不同......