当前没有测试数据。

题目背景

$\texttt{Slight Light, Slight Hope.}$

题目描述

小 W 有一棵 $n$ 个点的有根树（节点标号为 $1\sim n$），以 $1$ 号点为根。其中 $i$ 号点的点权为 $a_i$。

假设 $i$ 号点的父节点为 $f_i$（方便起见认为 $f_1=0$），小 W 发现这棵树有一个奇妙的性质：对于任意整数 $i\in[2,n]$，满足 $f_{i-1}\le f_i < i$。

小 C 对此很感兴趣，因此她决定进行 $q$ 次询问，第 $i$ 次询问给出一个区间 $[l_i,r_i]$，求：

$$\left(\sum_{x=l_i}^{r_i}\sum_{y=l_i}^{r_i}[l_i\le \operatorname{LCA}(x,y)\le r_i]\cdot a_x\cdot a_y\right)\bmod 998244353 $$

其中 $\operatorname{LCA}(x,y)$ 表示 $x$ 和 $y$ 的最近公共祖先。

因为小 C 在每次询问时都迫切地想要知道答案，所以本题强制在线（具体方式见输入格式）。

输入格式

第一行包含两个正整数 $n,q$，分别表示节点个数和询问次数。

第二行 $n$ 个非负整数 $a_{1\sim n}$，表示每个点的点权。

第三行 $n-1$ 个正整数 $f_{2\sim n}$，表示每个点的父节点。

接下来 $q$ 行，每行两个非负整数 $l_i',r_i'$。假设上一次询问的答案为 $\text{lst}$（对于第一个询问，认为 $\text{lst}=0$），则真正的 $l_i=l_i'\oplus \text{lst}$，$r_i=r_i'\oplus \text{lst}$，其中 $\oplus$ 表示按位异或运算。

输出格式

共 $q$ 行，每行一个整数表示对应询问的答案。（向 $998244353$ 取模）

样例

输入

6 3
1 2 3 4 5 6
1 1 2 2 3
1 2
11 12
131 132

输出

9
130
441

样例解释

第一个询问的区间为 $[1,2]$，$\operatorname{LCA}(1,1)=1,\operatorname{LCA}(1,2)=1,\operatorname{LCA}(2,1)=1,\operatorname{LCA}(2,2)=2$ 都符合条件。答案为 $1\times 1+1\times 2+2\times 1+2\times 2=9$。

第二个询问的区间为 $[2,5]$，$\operatorname{LCA}(2,2)=2,\operatorname{LCA}(2,4)=2,\operatorname{LCA}(2,5)=2,\operatorname{LCA}(3,3)=3,\operatorname{LCA}(4,2)=2,\operatorname{LCA}(4,4)=4,\operatorname{LCA}(4,5)=2,\operatorname{LCA}(5,2)=2,\operatorname{LCA}(5,4)=2,\operatorname{LCA}(5,5)=5$ 符合条件，其余点对 $\operatorname{LCA}$ 为 $1$。答案为 $130$。

第三个询问的区间为 $[1,6]$，由于 $\operatorname{LCA}$ 肯定在 $[1,n]$ 范围内，任意点对都满足条件。答案为 $441$。

数据范围与提示

• Subtask 1 ($20\%$)：$n,q\le 5\times 10^3$
• Subtask 2 ($20\%$)：$n,q\le 5\times 10^4$
• Subtask 3 ($20\%$)：树的形态随机
• Subtask 4 ($40\%$)：无特殊限制

对于 $100\%$ 的数据：

• $1\le n,q\le 2.5\times 10^5$
• $0\le a_i < 998244353$
• $1\le l_i\le r_i\le n$
• 保证对于任意整数 $i\in[2,n]$，满足 $f_{i-1}\le f_i < i$