Focal Energy Hubs on a Tree

Given an undirected weighted tree with (n) nodes and (n-1) edges, collectors are placed on a set of vertices. For a tree (G=(V,E)), consider a subset (S) of collectors (with (2\le|S|\le k)) and a vertex (v) (which is not in (S)). Let the unique simple path from each (u\in S) to (v) be given. Define the branch of (u) with respect to (v) as the neighbor of (v) on the path from (v) to (u) (denoted by (b_v(u))). The vertex (v) is called a focal point for (S) if the branches (b_v(u)) for all (u\in S) are pairwise distinct. For each focal point (v) of (S), an energy hub is built with cost

[ W_{S,v}=\prod_{u\in S} d(u,v), ]

where (d(u,v)) is the distance (the sum of edge weights) between (u) and (v). There are multiple schemes. In each scheme, collectors are placed on (c) nodes of the tree and a constant (k) is given. Then, for a number of queries, each query gives an integer (x). For each query, consider all subsets (S) of the collectors with (|S|= x) (note that only subsets with (2\le x\le k) yield hubs) and sum the cost (W_{S,v}) over all focal points (v) of (S). Output the total cost modulo (998244353).


Input Format:

• The first line contains an integer (n) (the number of nodes).
  
• The next (n-1) lines each contain three integers (u, v, w) describing an edge between nodes (u) and (v) with weight (w).
  
• Next, an integer (m) denotes the number of schemes.
  
• Then, for each scheme, the first line contains three integers (c, k, q): the number of collectors, the maximum subset size (k), and the number of queries.
  
• The following line contains (c) distinct integers indicating the nodes where collectors are placed.
  
• Then (q) lines follow, each containing an integer (x) representing a query (only subsets (S) of size (x) are considered).
  
  Output Format:
  For each query (in the order given, and schemes in order), output one line containing the total cost modulo (998244353).

inputFormat

The input begins with an integer (n) ((1\le n\le \text{small})) -- the number of nodes in the tree. The next (n-1) lines each contain three integers (u), (v) and (w) ((1\le u,v\le n), (w\ge 1)) representing an edge between (u) and (v) with weight (w). Then an integer (m) is given, representing the number of schemes. For each scheme, a line with three integers (c, k, q) is given, indicating the number of collectors, the maximum subset size (k), and the number of queries respectively. The next line contains (c) distinct integers specifying the nodes at which the collectors are placed. Finally, (q) lines follow, each with an integer (x) ((2\le x\le k)) representing the subset size for which the total cost of energy hubs is queried.

outputFormat

For each query (in the order they appear across all schemes), output a single integer, the total cost to build all the required energy hubs for subsets (S) of collectors of size (x), modulo (998244353).

sample

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

11
6