Problem Statement

Sambo, who lives in a village on the $xy$-plane, has decided to go out to a dangerous bamboo thicket nearby.

The bamboo thicket spreads over the locations whose $x$-coordinate and $y$-coordinate are both at least $0$ and at most $N$.
When Sambo is at $(x, y)$, he can move to $(x + 1, y)$ or $(x, y + 1)$.
His goal is to start from $(0, 0)$, pass through all $M$ checkpoints, and reach $(N, N)$.
The $i$-th checkpoint is at $(xc_i, yc_i)$.

However, moving through the bamboo thicket is not safe, because $L$ tigers live there.
The $i$-th tiger is lurking at $(xt_i, yt_i)$. A tiger may be at the location of a checkpoint. If Sambo comes to the same location as a tiger, he makes the tiger angry.
To calm the tiger down, Sambo must give it $1$ of the ornaments he is carrying. If he makes a tiger angry while he does not have even $1$ ornament, he will be eaten by the tiger!

Sambo starts with $K$ ornaments. How many ways are there for him to pass through all $M$ checkpoints and reach $(N, N)$ without being eaten by a tiger?
Since the answer can be very large, output it modulo $998244353$.

Input

$N \,\, M \,\, L \,\, K$
$xc_1 \,\, yc_1$
$xc_2 \,\, yc_2$
$\vdots$
$xc_M \,\, yc_M$
$xt_1 \,\, yt_1$
$xt_2 \,\, yt_2$
$\vdots$
$xt_L \,\, yt_L$

• $1 \leq N \leq 2×10^5$
• $0 \leq M \leq \min \left(10^5,N-1 \right)$
• $0 \leq L \leq \min \left(100, (N+1)^2 - 2 \right)$
• $0 \leq K \leq 10^5$
• $0 < xc_i,yc_i < N$
• $xc_i < xc_{i+1}$
• $yc_i < yc_{i+1}$
• $0 \leq xt_i,yt_i \leq N$
• $(xt_i,yt_i) \neq (0,0)$
• $(xt_i,yt_i) \neq (N,N)$
• If $i \neq j$, then $(xt_i,yt_i) \neq (xt_j,yt_j)$
• All input values are integers.

Output

Output on one line the total number of ways for Sambo to pass through all $M$ checkpoints and reach $(N, N)$ without being eaten by a tiger, modulo $998244353$. Print a newline at the end.

Sample

3 1 1 0
1 1
2 2

4

3 2 7 6
1 1
2 2
3 1
2 0
2 1
3 2
3 0
1 0
0 2

8

100 5 5 3
20 21
30 26
49 70
80 74
90 90
84 81
10 14
50 71
51 74
25 25

131095149