Дан простой связный неориентированный граф, являющийся кактусом: каждое ребро лежит не более чем на одном простом цикле. Этот кактус является треугольным: длина любого простого цикла не превышает 3.

Ответьте на запросы. В каждом запросе даны две вершины $s$ и $f$, а также целое число $k$. Найдите количество простых путей между вершинами $s$ и $f$ длины ровно $k$. Это число необходимо найти по модулю $998\,244\,353$.

Путь называется простым, если все его вершины различны; длина пути равна количеству ребер в нем.

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

Первая строка содержит два целых числа $n, m$ ($2 \le n \le 2 \cdot 10^5$, $n - 1 \le m \le \frac{3(n-1)}{2}$) — количество вершин и ребер в графе.

Каждая из следующих $m$ строк содержит два целых числа $u, v$ ($1 \le u, v \le n, u \neq v$), означающих, что в графе есть неориентированное ребро $(u, v)$. Все ребра различны. Гарантируется, что граф является связным треугольным кактусом.

Следующая строка содержит одно целое число $q$ ($1 \le q \le 2 \cdot 10^5$) — количество запросов.

Каждая из следующих $q$ строк содержит три целых числа $s, f, k$ ($1 \le s, f \le n$, $0 \le k < n$) — описание запроса.

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

Выведите $q$ целых чисел — ответы на запросы.

Примеры

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

8 10
1 2
2 3
3 1
3 4
4 5
5 6
6 4
4 7
7 8
8 4
6
1 1 0
1 1 1
1 4 3
6 2 4
5 7 4
3 4 2

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

1
0
1
2
1
0