跳蚤国王的密码本是一个长为 $n$，字符集为 $\{0,\dots ,p-1\}$ 的字符串。跳蚤国王考虑了一种简单的哈希算法，取底数为 $b$，字符串 $\mathbf{s}=s_0{s}_1\dots s_{n-1}$ 的哈希值就是 $H(\mathbf{s},b)=\sum _{i=0}^{n-1}{s}_i{b}^{i}modp$。接着，跳蚤国王随机生成了一个字符串 $\mathbf{s}$，并选取了数 $q$，带入哈希函数验证了 $b=1,q,\dots ,q^{n-1}$ 的这些情况。经过计算之后，跳蚤国王惊讶地发现仅对于 $k$ 个 $i$，$b=q^i$ 时的字符串哈希值不为 $0$。

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

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

本题取 $p=998244353$，且保证 $1,q,\dots ,q^{n-1}$ 在 $modp$ 下是互不相同的，可以证明此时 $s_m$ 被唯一确定。

输入格式

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

接下来 $k$ 行每行两个整数 $i,v$ 表示 $H(\mathbf{s},q^i)=v$。

输出格式

输出一个数 $s_m$。

样例一

input

3 0 3 10
0 6
1 123
2 10203

output

3

explanation

不难验证 $\mathbf{s}=\mathtt{\text{321}}$。因此 $s_0=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\mathrm{\%}$ 的数据，保证 $1\le n\le p-1,0\le m\le n-1,1\le k\le min(n,{10}^5),1\le q\le p-1,0\le i\le n-1,1\le v\le p-1$，且输入的 $i$ 互不相同，$1,q,\dots ,q^{n-1}$ 在 $modp$ 下互不相同。

时间限制：$3\mathtt{\text{s}}$

空间限制：$1\mathtt{\text{GB}}$

下载

样例数据下载