Bạn được cho một đồ thị vô hướng đơn, liên thông và là một cactus: mỗi cạnh nằm trên tối đa một chu trình đơn. Cactus này là tam giác: độ dài của bất kỳ chu trình đơn nào cũng không quá 3.

Hãy trả lời các truy vấn. Trong mỗi truy vấn, bạn được cho hai đỉnh $s$ và $f$, cùng một số nguyên $k$. Hãy tìm số lượng đường đi đơn giữa hai đỉnh $s$ và $f$ có độ dài đúng bằng $k$. Bạn cần tìm số này theo modulo $998\,244\,353$.

Đường đi được gọi là đơn nếu tất cả các đỉnh của nó đều phân biệt, độ dài của đường đi bằng số lượng cạnh trên đường đi đó.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n, m$ ($2 \le n \le 2 \cdot 10^5$, $n - 1 \le m \le \frac{3(n-1)}{2}$) — số lượng đỉnh và cạnh trong đồ thị.

Mỗi dòng trong $m$ dòng tiếp theo chứa hai số nguyên $u, v$ ($1 \le u, v \le n, u \neq v$), nghĩa là có một cạnh vô hướng $(u, v)$ trong đồ thị. Tất cả các cạnh đều phân biệt. Đảm bảo rằng đồ thị là một cactus tam giác liên thông.

Dòng tiếp theo chứa một số nguyên duy nhất $q$ ($1 \le q \le 2 \cdot 10^5$) — số lượng truy vấn.

Mỗi dòng trong $q$ dòng tiếp theo chứa ba số nguyên $s, f, k$ ($1 \le s, f \le n$, $0 \le k < n$) — mô tả của một truy vấn.

Dữ liệu ra

In ra $q$ số nguyên — câu trả lời cho các truy vấn.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

1
0
1
2
1
0