Tree Weight Update and Subtree Maximum Sum Queries

You are given a rooted tree with n nodes, rooted at node 1. Each node i has an initial weight c_i.

For every node u, define its value val(u) as the maximum c_i among all nodes in the subtree rooted at u (including u itself). Let f(x,y) be the sum of val(u) over all nodes of the tree after changing the weight of node x from c_x to y (only this weight is modified, all other nodes keep their original weight).

It can be observed that updating the weight of node x only affects the values of nodes that are ancestors of x. In particular, if we denote by A(x) the set of all ancestors of x (including x itself), and let M(u) be the original maximum weight in the subtree of u, then after the update the new value at node u becomes max(M(u), y). Therefore, we have:

\[ f(x,y)=f_0+\sum_{u\in A(x)}\Big(\max(y,M(u))-M(u)\Big), \]

where f₀ is the sum of M(u) over all nodes in the original tree.

You need to answer q queries. Each query is given by three integers l, r, a. For each query, you are to compute

\[ \sum_{i=l}^{r}f(a,i) \mod 998244353. \]

inputFormat

The first line contains two integers n and q (1 ≤ n, q ≤ 10⁵) — the number of nodes in the tree and the number of queries.

The second line contains n integers: c₁, c₂, ..., c_n (1 ≤ c_i ≤ 10⁹), where c_i is the weight of node i.

Then follow n-1 lines, each containing two integers u and v (1 ≤ u, v ≤ n) representing an edge between nodes u and v (the given graph is a tree with node 1 as its root).

Then follow q lines, each containing three integers l, r, and a (1 ≤ l ≤ r ≤ 10⁹, 1 ≤ a ≤ n) representing a query.

outputFormat

For each query, output a single line containing one integer: the answer modulo 998244353.

sample

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

43
50
55

</p>