火山哥在上小学数学时学习到了分式的求值方法，然后他注意到了一个很有意思的现象：$\frac{a}{\frac{b}{c}}$(即 $a/(b/c)$) 和 $\frac{\frac{a}{b}}{c}$(即$(a/b)/c$) 的值可能是不一样的！于是他开始思考，一个有 n 条横线的分式有什么有趣的性质。

我们可以用一个序列 $a[0...n]$ 和一个 $1...n$ 的排列 $p[1...n]$ 来定义一个 $n$ 重分式，其中 $p[i]$ 表示第 $i$ 条除法横线的长度，$a[i]$ 表示在第 $i+1$ 条横线上面的数的值，其中 $a[n]$ 表示最下面的数字的值。

例如 2重分式 $a/(b/c)$ 用上面方法来定义的话就是 $[a,b,c]$ 和 $[2,1]$

我们定义 $f(a,p)$ 表示该多重分式的值，例如 $f([1,2,3],[2,1])=3/2$，$f([1,2,3],[1,2])=1/6$，$f([2,3,4,5],[2,3,1])=5/6$

现在火山哥想知道的是，在给定 $a[0...n]$ 和 $p[1...n]$ 的情况下，如果每次给定 $1\leq l\leq r\leq n$，那么是否能快速算出 $f(a[l-1...r],p[l...r])$

由于分数有精度问题，你只需要输出答案对 $998244353$ 取模后的值。

输入格式

第一行两个整数 $n,Q$，表示横线的数量以及询问的个数

第二行 $n+1$ 个正整数，表示 $a[0...n]$

第三行一个长度为 $n$ 的排列，表示 $p[1...n]$

接下来 $Q$ 行，每行两个正整数 $l,r$，表示询问 $f(a[l-1...r],p[l...r])$

输出格式

对于每次询问，输出一行一个整数表示答案对 $998244353$ 取模后的值

样例数据

样例输入

3 6
2 4 6 8
3 2 1
1 1
1 2
1 3
2 2
2 3
3 3

样例输出

499122177
3
623902721
665496236
332748123
249561089

子任务

Task1 (12pts)：保证 $1\leq n,Q\leq 100$

Task2 (20pts)：保证 $1\leq n,Q\leq 2000$

Task3 (33pts)：保证数据随机

Task4 (15pts)：保证 $1\leq n,Q\leq 2\times 10^5$

Task5 (20pts)：保证 $1\leq n,Q\leq 5\times 10^5$

对于所有数据，保证 $p$ 是一个 $1...n$ 的排列，且 $1\leq a[i]< 998244353$，$1\leq l\leq r\leq n$