题目背景

搬运自 Code+ 第 6 次网络赛。

题目描述

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$ 的值。

6 2
7 9 10 6 2 5
1 4
2 5

6
24

提示

数据范围

任何时候，保证 $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$ 分）：无额外约束。