단순 연결 무방향 그래프인 선인장(cactus) 그래프가 주어집니다. 선인장 그래프란 각 간선이 최대 하나의 단순 사이클에 포함되는 그래프를 의미합니다. 이 선인장 그래프는 삼각형 선인장(triangular cactus)으로, 모든 단순 사이클의 길이는 최대 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)$를 의미하는 두 정수 $u, v$ ($1 \le u, v \le n, u \neq 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