When Volcano was in elementary school, he learned how to evaluate fractions and noticed an interesting phenomenon: the value of $\frac{a}{\frac{b}{c}}$ (i.e., $a/(b/c)$) can be different from the value of $\frac{\frac{a}{b}}{c}$ (i.e., $(a/b)/c$)! This led him to wonder about the interesting properties of a fraction with $n$ horizontal division bars.

We can define an $n$-fold fraction using a sequence $a[0...n]$ and a permutation $p[1...n]$ of $1...n$, where $p[i]$ represents the length of the $i$-th division bar, and $a[i]$ represents the value of the number above the $(i+1)$-th bar, with $a[n]$ representing the value at the very bottom.

For example, a 2-fold fraction $a/(b/c)$ defined this way uses $[a, b, c]$ and $[2, 1]$.

We define $f(a, p)$ as the value of this multiple fraction. For example, $f([1, 2, 3], [2, 1]) = 3/2$, $f([1, 2, 3], [1, 2]) = 1/6$, and $f([2, 3, 4, 5], [2, 3, 1]) = 5/6$.

Now, Volcano wants to know if, given $a[0...n]$ and $p[1...n]$, he can quickly calculate $f(a[l-1...r], p[l...r])$ for each given query $1 \leq l \leq r \leq n$.

Since fractions can have precision issues, you only need to output the answer modulo $998244353$.

Input

The first line contains two integers $n$ and $Q$, representing the number of division bars and the number of queries, respectively.

The second line contains $n+1$ positive integers, representing $a[0...n]$.

The third line contains a permutation of length $n$, representing $p[1...n]$.

The next $Q$ lines each contain two positive integers $l$ and $r$, representing the query for $f(a[l-1...r], p[l...r])$.

Output

For each query, output one integer per line representing the answer modulo $998244353$.

Constraints

• Task 1 (12 pts): $1 \leq n, Q \leq 100$
• Task 2 (20 pts): $1 \leq n, Q \leq 2000$
• Task 3 (33 pts): Data is guaranteed to be random
• Task 4 (15 pts): $1 \leq n, Q \leq 2 \times 10^5$
• Task 5 (20 pts): $1 \leq n, Q \leq 5 \times 10^5$
• For all data, $p$ is a permutation of $1...n$, $1 \leq a[i] < 998244353$, and $1 \leq l \leq r \leq n$.

Examples

Input 1

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

Output 1

499122177
3
623902721
665496236
332748123
249561089