UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#3752. Hack

Statistics 下载数据

Description

他突然发现比赛中有一个Hack功能:
在比赛过程中,若提交了一道题的代码,并且过了这道题的pretest,那么你可以选择“锁定”这
道题,而一旦“锁定”,这道题的代码就不能更改了,此时你可以查看其他选手此题的代码,你可以
对有问题的代码进行Hack,即构造一组数据,使得它不能Accepted。若Hack成功,会得到一些加
分,当然Hack失败是会扣分的。
这天Wayne又在参加比赛。A题是一道比较简单的字符串题目,Wayne在做出了此题后想尝
试 Hack,于是他点开了一些人的代码。他发现很多人用哈希过了pretest,而且大部分人的哈希算
法是这样的:
设字符串S,长度为N,设一个正整数P,那么计H=∑P^(N-i-1)*Si(其中0<=i<N)
符串下标从 0 开始,而Si代表对应字符的ASCII码值。注意H可能会很大,所以可以做一项简单
的处理,就是把Hmod 232 作为哈希值。
Wayne看到这些简单的代码非常不爽,所以他找了K个长度不超过L的字符串S,想知道是
否存在长度不超过L的字符串T,使得T不同于S但是哈希值相同。若有,他还想知道字典序最
小的T是什么。

Input

第一行三个正整数P,L和K。
接下来共K行,每行一个字符串S。

Output

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

Sample Input

32768 3 2
ZZZ
A

Sample Output

BZZ
-1

Hint

P<=2^31,L<=8,K<=15


Source