For a given source node $s$ and sink node $t$, a directed graph is called an "Almond" if and only if:

1. All nodes are reachable from $s$;
2. The in-degree of $s$ is $0$;
3. The out-degree of $t$ is $0$;
4. Every node except $s$ and $t$ has an in-degree of $1$ and an out-degree of $1$.

Given a directed graph $G$ with $n$ nodes and $m$ edges, where nodes are numbered from $1$ to $n$, and given the indices of $s$ and $t$ ($s \ne t$).

Answer $q$ queries. Each query provides a node $u$ ($u \ne s$), and you must find the number of "Almond subgraphs" $G'$ of $G$ such that there exists an edge $s \to u$ in $G'$. The answer should be taken modulo $998\,244\,353$.

Here, let $G=(V, E)$. $G'=(V', E')$ is called an "Almond subgraph" of $G$ if and only if:

1. $E' \subseteq E$;
2. $u \in V'$ if and only if there exists $v$ such that $E'$ contains an edge $u \to v$ or $v \to u$;
3. $s, t \in V'$, and $G'$ is an "Almond".

Input

The first line contains two integers $n$ and $m$.

The next line contains two integers, representing the indices of $s$ and $t$ respectively.

The next $m$ lines each contain two integers $u$ and $v$, representing a directed edge $u \to v$ in $G$.

The next line contains an integer $q$.

The next $q$ lines each contain an integer, representing the node index $u$ for a query.

Output

For each query, output a single integer on a new line representing the answer.

Examples

Input 1

5 10
1 5
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
4
2
3
4
5

Output 1

20
14
10
15

Constraints

For all data, $2 \le n \le 22$, $0 \le m \le 10\,000$, $0 \le q \le n$.

Subtask 1 (10 points): $n \le 11$, $m \le 20$;

Subtask 2 (10 points): $n \le 11$;

Subtask 3 (15 points): $n \le 17$;

Subtask 4 (10 points): $m=n^2$, each directed edge $u \to v$ appears exactly once;

Subtask 5 (15 points): $n \le 20$;

Subtask 6 (15 points): $q=1$;

Subtask 7 (25 points): No special restrictions.