Dany jest prosty spójny graf nieskierowany, który jest kaktusem: każda krawędź należy do co najwyżej jednego cyklu prostego. Ten kaktus jest trójkątny: długość każdego cyklu prostego wynosi co najwyżej 3.

Odpowiedz na zapytania. W każdym zapytaniu otrzymujesz dwa wierzchołki $s$ i $f$ oraz liczbę całkowitą $k$. Znajdź liczbę ścieżek prostych między wierzchołkami $s$ i $f$ o długości dokładnie $k$. Wynik należy podać modulo $998\,244\,353$.

Ścieżka jest prosta, jeśli wszystkie jej wierzchołki są różne, a długość ścieżki jest równa liczbie krawędzi na tej ścieżce.

Wejście

W pierwszej linii znajdują się dwie liczby całkowite $n, m$ ($2 \le n \le 2 \cdot 10^5$, $n - 1 \le m \le \frac{3(n-1)}{2}$) — liczba wierzchołków i krawędzi w grafie.

Każda z kolejnych $m$ linii zawiera dwie liczby całkowite $u, v$ ($1 \le u, v \le n, u \neq v$), co oznacza, że w grafie istnieje nieskierowana krawędź $(u, v)$. Wszystkie krawędzie są różne. Gwarantuje się, że graf jest spójnym kaktusem trójkątnym.

W kolejnej linii znajduje się pojedyncza liczba całkowita $q$ ($1 \le q \le 2 \cdot 10^5$) — liczba zapytań.

Każda z kolejnych $q$ linii zawiera trzy liczby całkowite $s, f, k$ ($1 \le s, f \le n, 0 \le k < n$) — opis zapytania.

Wyjście

Wypisz $q$ liczb całkowitych — odpowiedzi na zapytania.

Przykład

Wejście 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

Wyjście 1

1
0
1
2
1
0