Кодовая книга короля блох — это строка длины $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, изменить свой рейтинг на $8000$ и сделать так, чтобы король блох не смог войти в систему и изменить его обратно.

В этой задаче $p=998244353$, и гарантируется, что $1,q,\dots,q^{n-1}$ по модулю $p$ попарно различны. Можно доказать, что в этом случае $s_m$ определяется однозначно.

Входные данные

В первой строке содержатся четыре целых числа $n, m, k, q$. Они обозначают длину строки, индекс искомого символа, количество ненулевых хеш-значений и основание соответственно.

Далее следуют $k$ строк, каждая из которых содержит два целых числа $i$ и $v$, означающих, что $H(\mathbf{s}, q^i) = v$.

Выходные данные

Выведите одно число $s_m$.

Примеры

Пример 1

Входные данные

3 0 3 10
0 6
1 123
2 10203

Выходные данные

3

Примечание

Нетрудно проверить, что $\mathbf{s} = \texttt{321}$. Следовательно, $s_0=3$.

Пример 2

Входные данные

2 0 2 998244352
0 132
1 666

Выходные данные

399

Пример 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

Выходные данные

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}$ попарно различны по модулю $p$.