The Flea King's codebook is a string of length $n$ with a character set $\{0, \dots, p-1\}$. The Flea King considers a simple hashing algorithm with base $b$, where the hash value of a string $\mathbf{s}=s_0s_1\dots s_{n-1}$ is $H(\mathbf{s}, b)=\sum_{i=0}^{n-1} s_i b^i \bmod p$. The Flea King randomly generated a string $\mathbf{s}$ and chose a number $q$, then verified the hash function for the cases $b=1, q, \dots, q^{n-1}$. After calculation, the Flea King was surprised to find that the string hash value is non-zero for only $k$ values of $i$ where $b=q^i$.

This news reached Skip the Flea, who has stolen $p, q, n$ and the $k$ pairs of $(i, H(\mathbf{s}, q^i))$. Furthermore, Skip learned that $s_m$ is the login password for the Flea King's computer. Now, Skip needs to recover the value of $s_m$.

By doing this, Skip can sneak into the UOJ server, change its rating to $8000$, and prevent the Flea King from logging in to change it back.

In this problem, $p=998244353$, and it is guaranteed that $1, q, \dots, q^{n-1}$ are distinct modulo $p$. It can be proven that $s_m$ is uniquely determined under these conditions.

Input

The first line contains four integers $n, m, k, q$, representing the length of the string, the position of the string to query, the number of non-zero hash values, and the common ratio of the chosen base, respectively.

The next $k$ lines each contain two integers $i$ and $v$, representing $H(\mathbf{s}, q^i) = v$.

Output

Output a single integer $s_m$.

Examples

Input 1

3 0 3 10
0 6
1 123
2 10203

Output 1

3

Note 1

It is not difficult to verify that $\mathbf{s} = \texttt{321}$. Therefore, $s_0=3$.

Input 2

2 0 2 998244352
0 132
1 666

Output 2

399

Input 3

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 3

19212461

Constraints

For $100\%$ of the data, it is guaranteed that $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$. The input values of $i$ are distinct, and $1, q, \dots, q^{n-1}$ are distinct modulo $p$.