ノミの王のパスワードブックは、長さ $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 ノミに知れ渡り、Skip ノミは $p, q, n$ およびこれら $k$ 組の $(i, H(\mathbf{s}, q^i))$ の値を盗み出しました。さらに、Skip ノミは $s_m$ がノミの王のコンピュータのログインパスワードであることを突き止めました。今、Skip ノミは $s_m$ の値を復元する必要があります。

これができれば、Skip ノミは UOJ サーバーに侵入して自身のレーティングを $8000$ に書き換え、ノミの王がコンピュータにログインして元に戻せないようにすることができます。

本問では $p=998244353$ とし、$1,q,\dots,q^{n-1}$ が $\bmod p$ において互いに異なることを保証します。このとき、$s_m$ が一意に定まることが証明できます。

入力形式

入力は以下の形式で与えられます。

$n \ m \ k \ q$

$i_1 \ v_1$

$i_2 \ v_2$

$\vdots$

$i_k \ v_k$

1行目には4つの整数 $n, m, k, q$ が与えられます。それぞれ文字列の長さ、求める文字列の位置、非ゼロハッシュ値の数、および選ばれた底の公比を表します。

続く $k$ 行には、それぞれ $H(\mathbf{s}, q^i) = v$ を満たす $i$ と $v$ が与えられます。

出力形式

$s_m$ の値を1行で出力してください。

入出力例

入力 1

3 0 3 10
0 6
1 123
2 10203

出力 1

3

注記

$\mathbf{s} = \texttt{321}$ であることは容易に検証できます。したがって $s_0=3$ です。

入力 2

2 0 2 998244352
0 132
1 666

出力 2

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

出力 3

19212461

制約と注意

すべてのデータにおいて、$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$ において互いに異なります。