Given an undirected simple graph $G$, find the number of subsets of edges such that after keeping only these edges, the degree of every vertex is at least 2.

You need to answer this question for several induced subgraphs of $G$. The answer should be modulo $998244353$.

Input Format

The first line contains two positive integers $n$ and $m$, representing the number of vertices and edges in the graph.

The next $m$ lines each contain two positive integers $u$ and $v$, representing an edge.

The next line contains a positive integer $q$, representing the number of queries.

The next $q$ lines each contain a binary string of length $n$, where the $i$-th character is '1' if $i \in S$, and '0' otherwise. You are asked to process the induced subgraph of $S$. It is guaranteed that $S$ is non-empty.

Output Format

Output $q$ lines, each containing a single integer representing the answer.

Examples

Input 1

5 8
1 2
2 3
3 4
4 1
1 5
2 5
3 5
4 5
3
11111
01111
11110

Output 1

29
2
1

Subtasks

For $100\%$ of the data, it is guaranteed that $1\leq n\leq 19$, $1\leq m\leq \frac{n(n-1)}{2}$, and $1\leq q\leq 10^5$.