Since you cannot design a Gödel machine, you decide to solve a data structure problem first:

Given a sequence $a_1, \dots, a_n$ of length $n$. You need to answer $m$ queries. The $i$-th query provides an interval $[l_i, r_i]$. Please calculate the product of the greatest common divisors (GCDs) of all non-empty subsets of this interval. Since the answer can be very large, output the result modulo $998244353$ for each query.

Input

The first line contains two positive integers $n$ and $m$, as described above.

The next line contains $n$ positive integers describing the sequence $a_1, \dots, a_n$.

The next $m$ lines each contain $l_i$ and $r_i$, describing the $i$-th query.

Output

Output $m$ lines, each containing the result of the query modulo $998244353$.

Examples

Input 1

5 3
2 6 3 15 5
4 4
1 3
2 5

Output 1

15
216
546750

Input 2

6 6
3332 411 6666 6291 415 7180
4 6
1 5
5 6
4 4
1 2
1 3

Output 2

889738671
989336054
14898500
6291
1369452
867407130

Subtasks

Idea: ouuan&lk, Solution: ccz181078, Code: ouuan&lk, Data: ouuan&lk

For $10\%$ of the data, $n, m \le 10$.

For another $10\%$ of the data, $n, m \le 1000$.

For another $20\%$ of the data, $1 \le a_i \le 1000$.

For another $10\%$ of the data, for all $1 \le i < n$, $l_i \le l_{i+1} \le 10^5$ and $r_i \le r_{i+1} \le 10^5$.

For another $20\%$ of the data, $1 \le a_i \le 30000$.

For $100\%$ of the data, $1 \le n, m, a_i \le 10^5$ and $1 \le l_i \le r_i \le n$.