Lucky Tree Planting Plan

L school has a large avenue lined with trees. The new principal Lsy wants to beautify the environment by planting trees along the road inside the school gate. As part of his plan, a total of n trees are to be planted, with heights \(h_1, h_2, \ldots, h_n\). However, being very particular about feng shui, he has asked you, the feng shui master, to compute the lucky value of his plan.

For a sequence of n trees, the lucky value of an interval \([u,v]\) is defined as follows:

[ \text{Lucky}(u,v)= \begin{cases} 1, & \text{if } u = v,\ \prod\limits_{i=u}^{v-1}\prod\limits_{j=i+1}^{v} \gcd(h_i,h_j), & \text{if } u < v. \end{cases} ]

You are given q queries, each containing an interval \([u,v]\). For each query, output the lucky value modulo \(998244353\).

inputFormat

The first line contains two integers \(n\) and \(q\) (the number of trees and the number of queries).

The second line contains \(n\) integers: \(h_1, h_2, \ldots, h_n\), where \(h_i\) represents the height of the \(i\)-th tree.

Each of the next \(q\) lines contains two integers \(u\) and \(v\) representing a query interval (1-indexed).

outputFormat

For each query, output a single integer: the lucky value of the given interval modulo \(998244353\).

sample

3 3
2 3 4
1 1
1 2
1 3

1
1
2