给定一个简单有向图 $G = (V, E)$，其中 $V = \{0, 1, 2, \dots, n - 1\}$ 且 $|E| = m$。 如果 $a, b, c \in V$ 满足以下所有限制： $b \neq c$ $(a \to b) \in E$ $(a \to c) \in E$ $(b \to c) \notin E$

那么我们将边 $b \to c$ 加入到边集 $E$ 中。 不断重复此操作，直到无法继续为止。可以证明最终得到的图 $G' = (V, E')$ 是唯一的。 接下来有 $q$ 次询问。对于每次询问，给定节点 $u, v \in V$。你需要回答在 $G'$ 中从 $u$ 到 $v$ 的简单路径（即不经过重复节点的路径）数量。 由于答案可能非常大，你只需要告诉我们答案对 $S$ 取模的结果。

输入格式

第一行包含四个整数 $n, m, q$ 和 $S$ ($1 \le n \le 5 \times 10^5, 0 \le m \le 10^6, 1 \le q \le 10^6, 1 \le S \le 2^{30}$)。 接下来的 $m$ 行给出 $E$ 中的每条边。每行包含两个整数 $u$ 和 $v$ ($0 \le u, v \le n - 1, u \neq v$)，表示图中的一条边 $u \to v$。保证图中没有重边或自环。 接下来的 $q$ 行描述所有询问。每行包含两个整数 $u$ 和 $v$ ($0 \le u, v \le n - 1$)。

输出格式

输出 $q$ 行。第 $i$ 行包含一个整数，表示答案对 $S$ 取模的结果。

样例

输入格式 1

11 9 30 998244353
0 1
0 2
3 4
5 4
6 5
7 8
8 9
9 8
10 9
0 1
0 2
1 0
1 2
2 0
2 1
3 4
3 5
3 6
4 3
4 5
4 6
5 3
5 4
5 6
6 3
6 4
6 5
7 8
7 9
7 10
8 7
8 9
8 10
9 7
9 8
9 10
10 7
10 8
10 9

输出格式 1

2
2
0
1
0
1
1
0
0
0
0
0
0
1
0
0
1
1
1
1
0
0
1
0
0
1
0
0
1
1