bzoj#P3752. Hack

Hack

题目描述

他突然发现比赛中有一个 Hack 功能:

在比赛过程中,若提交了一道题的代码,并且过了这道题的 pretest,那么你可以选择“锁定”这道题,而一旦“锁定”,这道题的代码就不能更改了,此时你可以查看其他选手此题的代码,你可以对有问题的代码进行 Hack,即构造一组数据,使得它不能 Accepted。若 Hack 成功,会得到一些加分,当然 Hack 失败是会扣分的。

这天 Wayne 又在参加比赛。A 题是一道比较简单的字符串题目,Wayne 在做出了此题后想尝试 Hack,于是他点开了一些人的代码。他发现很多人用哈希过了 pretest,而且大部分人的哈希算法是这样的:

设字符串 SS,长度为 nn,设一个正整数 pp,那么计 h=p(ni1)×Si (0i<n)h=\sum p^{(n-i-1)}\times S_i~(0 \le i < n)

字符串下标从 00 开始,而 SiS_i 代表对应字符的 ASCII 码值。注意 hh 可能会很大,所以可以做一项简单的处理,就是把 hmod232h \bmod 2^{32} 作为哈希值。

Wayne看到这些简单的代码非常不爽,所以他找了 kk 个长度不超过 ll 的字符串 SS,想知道是否存在长度不超过 LL 的字符串 TT,使得 TT 不同于 SS 但是哈希值相同。若有,他还想知道字典序最小的 TT 是什么。

输入格式

第一行三个正整数 ppllkk。 接下来共 kk 行,每行一个字符串 SS

输出格式

对每个字符串 SS 输出一行。
若找得到字符串 TT,则输出字典序最小的;否则输出 -1

32768 3 2
ZZZ
A
BZZ
-1

数据规模与约定

对于 100%100\% 的数据,p231p \le 2^{31}l8l \le 8k15k \le 15