Dany jest nieskierowany graf prosty $G$. Ile istnieje podzbiorów zbioru krawędzi takich, że po ich pozostawieniu stopień każdego wierzchołka wynosi co najmniej $2$?

Musisz odpowiedzieć na to pytanie dla kilku podgrafów indukowanych grafu $G$. Wynik należy podać modulo $998244353$.

Wejście

W pierwszej linii znajdują się dwie liczby całkowite $n$ oraz $m$, oznaczające odpowiednio liczbę wierzchołków i liczbę krawędzi w grafie.

Następnie $m$ linii zawiera po dwie liczby całkowite $u, v$, opisujące krawędź między wierzchołkami $u$ i $v$.

W kolejnej linii znajduje się liczba całkowita $q$, oznaczająca liczbę zapytań.

Następnie $q$ linii zawiera ciąg binarny o długości $n$, gdzie $i$-ty znak wynosi $1$, jeśli $i \in S$, w przeciwnym razie $i \notin S$. Zapytanie dotyczy podgrafu indukowanego przez zbiór $S$. Gwarantuje się, że $S$ jest niepusty.

Wyjście

Dla każdego zapytania wypisz w osobnej linii wynik modulo $998244353$.

Przykład

Wejście 1

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

Wyjście 1

29
2
1

Podzadania

Dla $100\%$ danych wejściowych zachodzi $1\leq n\leq 19$, $1\leq m\leq \frac{n(n-1)}{2}$ oraz $1\leq q\leq 10^5$.