题目背景

$\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)\bmod998244353 $$

其中 $\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'$。假设上一次询问的答案为 $lst$（对于第一个询问，认为 $lst=0$），则真正的 $l_i=l_i'\oplus lst$，$r_i=r_i'\oplus lst$，其中 $\oplus$ 表示按位异或运算。

输出格式

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

样例

input

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

output

9
130
441

explanation

第一个询问的区间为 $[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\times2+2\times1+2\times2=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 \leq 5\times10^3$
• Subtask $2$ ($20\%$) ：$n,q \leq 5\times10^4$
• Subtask $3$ ($20\%$) ：树的形态随机
• Subtask $4$ ($40\%$) ：无特殊限制

对于 $100\%$ 的数据，$1\le n,q\le2.5\times10^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$。