跳蚤国王的密码本是一个长为 $n$，字符集为 $\{0, \dots, p-1\}$ 的字符串。跳蚤国王考虑了一种简单的哈希算法，取底数为 $b$，字符串 $\mathbf{s}=s_0s_1\dots s_{n-1}$ 的哈希值就是 $H(\mathbf{s}, b)=\sum_{i=0}^{n-1} s_i b^i \bmod p$。接着，跳蚤国王随机生成了一个字符串 $\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}$ 在 $\bmod p$ 下是互不相同的，可以证明此时 $s_m$ 被唯一确定。

输入格式

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

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

输出格式

输出一个数 $s_m$。

3 0 3 10
0 6
1 123
2 10203

3

不难验证 $\mathbf{s} = \texttt{321}$。因此 $s_0=3$。

2 0 2 998244352
0 132
1 666

399

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

19212461

限制与约定

对于 $100\%$ 的数据，保证 $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}$ 在 $\bmod p$ 下互不相同。

时间限制：$3\texttt{s}$

空间限制：$1\texttt{GB}$

下载

样例数据下载