给定一个简单的连通无向图，它是一个仙人掌图：每条边最多属于一个简单环。该仙人掌图是三角的：任意简单环的长度最多为 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