给定一棵以 1 为根，由 n 个点组成的有根树，每个点有点权 ci 。
定义每个点的 val 值为：以它为根的子树内所有 ci 的最大值。
定义函数 f(x,y) 表示将 cx 改为 y 后整棵树的 val 值之和。
现在请您回答 q 组询问，每次询问给定 3 个量 (l,r,a) ，请求出∑(i=l, r)f(a,i) 对 998,244,353 取模的结果。

本题强制在线
第一行三个正整数，n、q 和 opt，分别表示树的点数、询问数和控制强制在线的量。
第二行 n 个正整数，表示每个点的点权。
接下来 n−1 行，每行两个正整数 ui 和 vi，表示树的每一条边。
接下来 q 行，每行三个正整数 l′,r′,a′ ，请计算出真实的 l,r,a 后完成询问。

• l=((l′+opt×lastans)mod n) +1
• r=((r′+opt×lastans)mod n) +1
• a=((a′+opt×lastans)mod n) +1

其中 lastans 表示上一组询问的答案，初始为 0 。
如果此时出现 l>r 的情况，请交换 l 和 r 。

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

样例解释：


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

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

数据范围：
对于 10% 的数据：1≤n,q≤100 。
对于 20% 的数据：1≤n,q≤3000 。
对于另 20% 的数据：1≤l′,r′,ci≤2 。
对于另 20% 的数据：l′=r′ 。
对于前 80% 的数据：opt=0 。
对于 100% 的数据：1≤n,q≤5×10⁵，1≤ci,a′,l′,r′≤n 。

P6798 数据结构 线段树 树状数组