P11443 [Code+#6] 校门外的树

搬运自 [Code+ 第 6 次网络赛](https://gitlink.org.cn/thusaa/codeplus6/)。

L 校门外有一条大马路，路边种了许多的树。L 校的新校长 Lsy 认为学校应该在校门内的马路边种许多的树来绿化环境。在他的植树计划中，共需种植 $n$ 棵树，每棵树都有一个高度 $h_{i}$。然而他是一个很信风水的人，为了保证校园的风水，他请来了作为风水大师的你来为他计算这个植树方案的幸运值。 对于 $n$ 棵树组成的序列，定义其中一个区间 $[u ,v]$ 的幸运值为： $$\prod\limits_{i=u}^{v-1}\prod\limits_{j=i+1}^{v}\operatorname{gcd}(h_i,h_j)$$ 如果 $u = v$ 则幸运值为 $1$。 现在你需要回答 L 校长对于 $q$ 个区间的询问，对于每个询问回答该区间幸运值 $\bmod 998244353$ 的值。

第一行为两个整数 $n,q$。 第二行为 $n$ 个整数 $h_{i}$。 接下来 $q$ 行，每行两个整数 $u,v$，表示 $q$ 次询问。

对于每个询问输出一行，为该区间的幸运值 $\bmod 998244353$ 的值。

### 数据范围 任何时候，保证 $1 \leq n,q, h_{i}\leq 10^5$。 每个子任务的额外约定： - Subtask1（$10$ 分）：$n,q \leq 100$。 - Subtask2（$10$ 分）：$h_{i}$ 全部相等。 - Subtask3（$15$ 分）：$h_{i} \leq 10^3$。 - Subtask4（$10$ 分）：$q = 1$。 - Subtask5（$25$ 分）：$n, q \leq3\times10^4$。 - Subtask6（$30$ 分）：无额外约束。