Дан неориентированный простой граф $G$. Найдите количество подмножеств множества рёбер таких, что после их оставления степень каждой вершины в графе будет $\geq 2$.

Вам необходимо ответить на этот вопрос для нескольких порождённых подграфов графа $G$. Ответы выведите по модулю $998244353$.

Входные данные

Первая строка содержит два целых положительных числа $n$ и $m$, обозначающих количество вершин и рёбер в графе соответственно.

Следующие $m$ строк содержат по два целых положительных числа $u, v$, описывающих ребро.

Следующая строка содержит целое положительное число $q$, количество запросов.

Следующие $q$ строк содержат по одной строке из 01 длиной $n$, где $i$-й символ равен $1$, если $i \in S$, и $0$ в противном случае. Необходимо найти ответ для порождённого подграфа, индуцированного множеством вершин $S$. Гарантируется, что $S$ не пусто.

Выходные данные

Выведите $q$ строк, каждая из которых содержит ответ на соответствующий запрос.

Примеры

Пример 1

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

Выходные данные 1

29
2
1

Подзадачи

Для $100\%$ данных гарантируется, что $1\leq n\leq 19$, $1\leq m\leq \frac{n(n-1)}{2}$, $1\leq q\leq 10^5$.