Se le proporciona un grafo simple, conexo y no dirigido que es un cactus: cada arista pertenece a, como máximo, un ciclo simple. Este cactus es triangular: la longitud de cualquier ciclo simple es como máximo 3.

Responda las consultas. En cada consulta, se le proporcionan dos vértices $s$ y $f$, y un entero $k$. Encuentre el número de caminos simples entre los vértices $s$ y $f$ con una longitud exactamente igual a $k$. Debe encontrar este número módulo $998\,244\,353$.

Un camino es simple si todos sus vértices son distintos; la longitud del camino es igual al número de aristas en el camino.

Entrada

La primera línea contiene dos enteros $n, m$ ($2 \le n \le 2 \cdot 10^5$, $n - 1 \le m \le \frac{3(n-1)}{2}$) — el número de vértices y aristas en el grafo.

Cada una de las siguientes $m$ líneas contiene dos enteros $u, v$ ($1 \le u, v \le n, u \neq v$), lo que significa que existe una arista no dirigida $(u, v)$ en el grafo. Todas las aristas son distintas. Se garantiza que el grafo es un cactus triangular conexo.

La siguiente línea contiene un único entero $q$ ($1 \le q \le 2 \cdot 10^5$) — el número de consultas.

Cada una de las siguientes $q$ líneas contiene tres enteros $s, f, k$ ($1 \le s, f \le n, 0 \le k < n$) — la descripción de una consulta.

Salida

Imprima $q$ enteros — las respuestas a las consultas.

Ejemplos

Entrada 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

Salida 1

1
0
1
2
1
0