Księga kodów Króla Pcheł to ciąg znaków o długości $n$ nad alfabetem $\{0, \dots, p-1\}$. Król Pcheł rozważał prosty algorytm haszujący z podstawą $b$, w którym wartość haszująca ciągu $\mathbf{s}=s_0s_1\dots s_{n-1}$ wynosi $H(\mathbf{s}, b)=\sum_{i=0}^{n-1} s_i b^i \bmod p$. Następnie Król Pcheł wygenerował losowy ciąg $\mathbf{s}$ i wybrał liczbę $q$, po czym zweryfikował wartości haszujące dla $b=1,q,\dots,q^{n-1}$. Po obliczeniach Król Pcheł ze zdziwieniem odkrył, że tylko dla $k$ wartości $i$ hasz ciągu przy $b=q^i$ jest różny od $0$.

Wiadomość ta dotarła do Pchły Skip, która wykradła wartości $p, q, n$ oraz $k$ par $(i, H(\mathbf{s}, q^i))$. Ponadto dowiedziała się, że $s_m$ jest hasłem do komputera Króla Pcheł. Teraz Pchła Skip musi odtworzyć wartość $s_m$.

Dzięki temu będzie mogła włamać się na serwer UOJ, zmienić swój ranking na $8000$ i uniemożliwić Królowi Pcheł zalogowanie się do komputera w celu przywrócenia zmian.

W zadaniu przyjmujemy $p=998244353$. Gwarantuje się, że wartości $1,q,\dots,q^{n-1}$ są parami różne modulo $p$. Można dowieść, że w takich warunkach wartość $s_m$ jest wyznaczona jednoznacznie.

Wejście

W pierwszej linii podano cztery licznie całkowite $n, m, k, q$. Oznaczają one odpowiednio długość ciągu, indeks szukanego znaku, liczbę niezerowych wartości haszujących oraz podstawę potęgowania.

W kolejnych $k$ liniach znajdują się dwie liczby całkowite $i, v$ oznaczające, że $H(\mathbf{s}, q^i) = v$.

Wyjście

Wypisz jedną liczbę $s_m$.

Przykład

Wejście 1

3 0 3 10
0 6
1 123
2 10203

Wyjście 1

3

Uwagi 1

Łatwo sprawdzić, że $\mathbf{s} = \texttt{321}$. Zatem $s_0=3$.

Wejście 2

2 0 2 998244352
0 132
1 666

Wyjście 2

399

Wejście 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

Wyjście 3

19212461

Ograniczenia

Dla $100\%$ danych wejściowych zachodzi $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$. Podane wartości $i$ są parami różne, a wartości $1,q,\dots,q^{n-1}$ są parami różne modulo $p$.