Vous disposez d'un graphe simple, connexe et non orienté qui est un cactus : chaque arête appartient au plus à un cycle simple. Ce cactus est triangulaire : la longueur de tout cycle simple est au plus 3.

Répondez aux requêtes. Dans chaque requête, vous recevez deux sommets $s$ et $f$, ainsi qu'un entier $k$. Trouvez le nombre de chemins simples entre les sommets $s$ et $f$ ayant une longueur exactement égale à $k$. Vous devez trouver ce nombre modulo $998\,244\,353$.

Un chemin est simple si tous ses sommets sont distincts ; la longueur du chemin est égale au nombre d'arêtes sur le chemin.

Entrée

La première ligne contient deux entiers $n, m$ ($2 \le n \le 2 \cdot 10^5$, $n - 1 \le m \le \frac{3(n-1)}{2}$) — le nombre de sommets et d'arêtes dans le graphe.

Chacune des $m$ lignes suivantes contient deux entiers $u, v$ ($1 \le u, v \le n, u \neq v$), signifiant qu'il existe une arête non orientée $(u, v)$ dans le graphe. Toutes les arêtes sont distinctes. Il est garanti que le graphe est un cactus triangulaire connexe.

La ligne suivante contient un entier unique $q$ ($1 \le q \le 2 \cdot 10^5$) — le nombre de requêtes.

Chacune des $q$ lignes suivantes contient trois entiers $s, f, k$ ($1 \le s, f \le n$, $0 \le k < n$) — la description d'une requête.

Sortie

Affichez $q$ entiers — les réponses aux requêtes.

Exemples

Entrée 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

Sortie 1

1
0
1
2
1
0