GCD Subset Product

Given a sequence \(a_1, a_2, \dots, a_n\), you need to answer \(m\) queries. In the \(i\)-th query, you are given a range \([l_i, r_i]\). For each query, consider every non-empty subset \(S\) of the subarray \(a_{l_i}, a_{l_i+1}, \dots, a_{r_i}\); let \(g(S)\) be the greatest common divisor (gcd) of all its elements. You are required to compute the product

[ \prod_{\substack{S \subseteq {l_i, l_i+1, \dots, r_i} \ S \neq \emptyset}} g(S) \mod 998244353. ]

It can be shown that the answer can be computed using multiplicative functions and inclusion-exclusion. In particular, if for any integer \(d\) we define \(f(d)\) as the number of elements in the given range divisible by \(d\), then the number of non-empty subsets whose gcd is divisible by \(d\) is \(2^{f(d)}-1\). By applying an inclusion-exclusion technique, one may compute for each \(d\) the number \(g(d)\) of subsets with \(\gcd(S)=d\), and the answer is then

[ \prod_{d=1}^{\max(a)} d^{g(d)} \mod 998244353. ]

inputFormat

The first line contains two integers \(n\) and \(m\): the length of the sequence and the number of queries.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\).

Each of the next \(m\) lines contains two integers \(l_i\) and \(r_i\), representing a query.

outputFormat

For each query, output a single line containing the required product modulo 998244353.

sample

3 2
2 4 8
1 2
2 3

8
64