UOJ Logo Universal Online Judge

UOJ

#658. 【ULR #2】哈希杀手

附件下载 统计

跳蚤国王的密码本是一个长为 n,字符集为 {0,,p1} 的字符串。跳蚤国王考虑了一种简单的哈希算法,取底数为 b,字符串 s=s0s1sn1 的哈希值就是 H(s,b)=i=0n1sibimodp。接着,跳蚤国王随机生成了一个字符串 s,并选取了数 q,带入哈希函数验证了 b=1,q,,qn1 的这些情况。经过计算之后,跳蚤国王惊讶地发现仅对于 kib=qi 时的字符串哈希值不为 0

这个消息被 Skip 蚤知道了,并且它已经窃取到了 p,q,n 和这 k(i,H(s,qi)) 的值。此外,它还得知 sm 就是跳蚤国王的电脑登录密码。现在 Skip 蚤需要还原出 sm 的值。

这样,它就可以潜入 UOJ 服务器并把自己的 rating 改为 8000 ,并让跳蚤国王无法登陆电脑改回来了。

本题取 p=998244353,且保证 1,q,,qn1modp 下是互不相同的,可以证明此时 sm 被唯一确定。

输入格式

第一行输入四个整数 n,m,k,q。分别表示字符串的长度,询问字符串位置,非零哈希值数量,以及所选的底数公比。

接下来 k 行每行两个整数 i,v 表示 H(s,qi)=v

输出格式

输出一个数 sm

样例一

input

3 0 3 10
0 6
1 123
2 10203

output

3

explanation

不难验证 s=321。因此 s0=3

样例二

input

2 0 2 998244352
0 132
1 666

output

399

样例三

input

2000 0 10 3
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 10

output

19212461

限制与约定

对于 100% 的数据,保证 1np1,0mn1,1kmin(n,105),1qp1,0in1,1vp1,且输入的 i 互不相同,1,q,,qn1modp 下互不相同。

子任务编号 n k 特殊性质 分值
1 2×103 5
2 106 1 10
3 107 5
4 p1 15
5 106 105 10
6 107 20
7 p1 qn=1 10
8 2×103 15
9 105 10

时间限制3s

空间限制1GB

下载

样例数据下载