F-Kevin的哈希构造_牛客小白月赛73

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

氧气少年最近喜欢上了哈希。

对于一个长度为 $len$ 的只包含小写英文字母的字符串，在给出了 $b(1\leq b\leq 10^9),p(1\leq p\leq 1000)$ 的数值的情况下，氧气少年计算这个字符串哈希 $hash$ 的公式如下：

$hash=(s_1\cdot b^{len-1}+s_2\cdot b^{len-2}+\dots +s_{len}\cdot b^{0})\mod p$

其中， $s_i$ 表示该字符串第 $i$ 个字符在小写字母表中的位置（例如： $\tt a$ 在字母表中的位置为 $1$ ）。

现在，氧气少年有一个长度为 $n(1\leq n \leq 50)$ 的字符串 $S$ 。请你帮他找到一个字符串 $T$ ， $T$ 应该满足如下条件：

$T$ 的长度为 $n$ 。
$T$ 只包含小写英文字母。
$T$ 的哈希与 $S$ 的哈希相同。
$T$ 和 $S$ 恰好有 $k(0\leq k\leq n)$ 个位置相同。换句话说，需要保证 $\sum_{i=1}^{n}[S_i=T_i]\ =k$ 。

如果没有符合要求的字符串，输出" $\tt -1$ "；如果有多个可行的答案，请输出任意一个。

输入描述:

第一行包含一个整数 ，表示测试用例的组数。

对于每组测试用例：

第一行包含四个整数 ；

第二行包含一个长度为  的字符串 ，保证  只包含小写英文字母。

保证对于所有的测试用例， 的总和不超过 。

输出描述:

对于每组测试用例：

仅输出一行。如果没有符合要求的字符串，输出""；否则请输出你找到的字符串。如果有多个可行的答案，请输出任意一个。

示例1

输入

复制

5
5 27 997 4
baaac
9 998244353 19 9
moonlight
9 998244353 19 8
kevinbaby
7 998244353 19 6
ancheng
11 998244353 19 6
protectemmm

输出

复制

-1
moonlight
kevinbtby
tncheng
prvtecbeswo