Description

Given a rooted tree with root $1$ and $n$ nodes. Each node has a weight $c_{i}$.

Define the value $val$ of each node as: the maximum $c_{i}$ among all nodes in the subtree rooted at this node.

Define the function $f(x,y)$ as the sum of $val$ over the entire tree after changing $c_{x}$ to $y$.

Now you need to answer $q$ queries. Each query gives three values $(l,r,a)$, and you need to compute $\sum\limits_{i=l}^{r}{f(a,i)}$ modulo $998,244,353$.

Input Format

This problem is forced online.

The first line contains three positive integers $n$, $q$, and $opt$, representing the number of nodes in the tree, the number of queries, and a value controlling the forced-online behavior.

The second line contains $n$ positive integers, representing the weight of each node.

The next $n - 1$ lines each contain two positive integers $u_{i}$ and $v_{i}$, representing an edge of the tree.

The next $q$ lines each contain three positive integers $l', r', a'$. You need to compute the real $l, r, a$ and then answer the query.

• $l = (( l' + opt \times lastans )\bmod n ) + 1$
• $r = (( r' + opt \times lastans )\bmod n ) + 1$
• $a = (( a' + opt \times lastans )\bmod n ) + 1$

Here, $lastans$ is the answer to the previous query, initially $0$.

If $l > r$, swap $l$ and $r$.

Output Format

For each query, output the final answer.

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

42
48
52

Hint

Sample Explanation

The real $(l,r,a)$ are:

• $(2,4,1)$
• $(3,5,2)$
• $(2,4,5)$

Constraints

For $10\%$ of the testdata: $1 \leq n,q \leq 100$。
For $20\%$ of the testdata: $1 \leq n,q \leq 3000$。
For another $20\%$ of the testdata: $1 \leq l',r',c_{i} \leq 2$。
For another $20\%$ of the testdata: $l' = r'$。
For the first $80\%$ of the testdata: $opt = 0$。
For $100\%$ of the testdata: $1 \leq n,q \leq 5 \times 10^{5}$, $1 \leq c_{i}, a', l', r' \leq n$。

Translated by ChatGPT 5