给定一个 $n$ 行 $m$ 列的网格图。大部分边是有向的，这意味着你可以从 $(x, y)$ 走到 $(x+1, y)$ 或 $(x, y+1)$。有 $k$ 条水平边是双向的，这意味着你既可以从 $(x, y)$ 走到 $(x, y+1)$，也可以从 $(x, y+1)$ 走到 $(x, y)$。保证不存在两条共享端点的双向边。

你需要找到 $l$ 条顶点不相交的简单路径，其中第 $i$ 条路径从 $(1, a_i)$ 到 $(n, b_i)$。对于一组路径，如果某条双向边的两个端点都没有被这组路径中的任何路径访问，则称该双向边为“坏边”。

输出所有不包含任何坏边的 $l$ 条顶点不相交简单路径的数量，对 $998244353$ 取模。

输入格式

第一行包含 $n, m, l, k$ ($2 \le n, m \le 100, 1 \le l \le 50, 0 \le k \le 50$)。

第二行包含 $a_1, a_2, \dots, a_l$ ($1 \le a_1 < a_2 < \dots < a_l \le m$)。

第三行包含 $b_1, b_2, \dots, b_l$ ($1 \le b_1 < b_2 < \dots < b_l \le m$)。

接下来的 $k$ 行，每行包含 $x_i, y_i$ ($1 \le x_i \le n, 1 \le y_i < m$)，表示从 $(x_i, y_i)$ 到 $(x_i, y_i+1)$ 的边是双向的。

保证不存在两条共享端点的双向边。

输出格式

一个整数——即答案。

样例

输入 1

2 2 1 2
2
1
1 1
2 1

输出 1

2

输入 2

3 4 2 1
1 4
1 4
2 2

输出 2

0

输入 3

10 10 3 4
1 2 3
8 9 10
2 3
2 5
4 6
7 8

输出 3

388035318