Given a tree with ~N~ nodes, conveniently numbered from 1 to ~N~, node ~1~ is the root node. You need to answer ~Q~ queries. Each query is in the form u v k, which is ~\sum{ \text{depth(i)} ^ k}~ where node ~i~ is on the path from ~u~ to ~v~, i.e. adding up the ~k~-th power of the depth of each node along the path from ~u~ to ~v~.

Input Specification

The first line contains one integer, ~N~, (~1 \le N \le 300,000~), the number of nodes in the tree.

Each of the following ~N-1~ lines contains two integers, ~u~ and ~v~ (~1 \le u, v \le N~), an edge between ~u~ and ~v~.

The next line contains one integer, ~Q~, (~1 \le Q \le 300,000~), the number of queries.

Each of the following ~Q~ lines contains three integers, ~u~, ~v~, and ~k~, (~1 \le u, v \le N~, ~1 \le k \le 50~).

Output Specification

Print one integer for each query, the sum modulo ~998244353~.

Sample Input

5
1 2
1 3
2 4
2 5
2
1 4 5
5 4 3

Sample Output

33
17

Explanation

For the tree in the sample input, the depth of each node is: ~dep[1] = 0~, ~dep[2] = 1~, ~dep[3] = 1~, ~dep[4] = 2~, ~dep[5] = 2~.

For the first query, the path is 1-->2-->4. Thus, the sum is ~ (0^5 + 1^5 + 2^5) \mod 998244353 = 33~.

For the second query, the path is 5-->2-->4. Thus, the sum is ~(2^{3} + 1^{3} + 2^{3}) \mod 998244353 = 17~.