题目描述

给定一棵以 $1$ 为根，由 $n$ 个点组成的有根树，每个点有点权 $c_{i}$ 。

定义每个点的 $val$ 值为：以它为根的子树内所有 $c_{i}$ 的最大值。

定义函数 $f(x,y)$ 表示将 $c_{x}$ 改为 $y$ 后整棵树的 $val$ 值之和。

现在请您回答 $q$ 组询问，每次询问给定 $3$ 个量 $(l,r,a)$ ，请求出 $\sum\limits_{i=l}^{r}{f(a,i)}$ 对 $998,244,353$ 取模的结果。

输入格式

本题强制在线

第一行三个正整数，$n$、$q$ 和 $opt$，分别表示树的点数、询问数和控制强制在线的量。

第二行 $n$ 个正整数，表示每个点的点权。

接下来 $n-1$ 行，每行两个正整数 $u_{i}$ 和 $v_{i}$，表示树的每一条边。

接下来 $q$ 行，每行三个正整数 $l',r',a'$ ，请计算出真实的 $l,r,a$ 后完成询问。

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

其中 $lastans$ 表示上一组询问的答案，初始为 $0$ 。

如果此时出现 $l > r$ 的情况，请交换 $l$ 和 $r$ 。

输出格式

对于每组询问，输出最终的答案。

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

提示

样例解释

真实的 $(l,r,a)$ 为：

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

数据范围

对于 $10\%$ 的数据：$1 \leq n,q \leq 100$ 。
对于 $20\%$ 的数据：$1 \leq n,q \leq 3000$ 。
对于另 $20\%$ 的数据：$1 \leq l',r',c_{i} \leq 2$ 。
对于另 $20\%$ 的数据：$l'=r'$ 。
对于前 $80\%$ 的数据：$opt=0$ 。
对于 $100\%$ 的数据：$1 \leq n,q \leq 5 \times 10^{5} ，1 \leq c_{i} , a' , l' , r' \leq n$ 。