由于你不会设计哥德尔机，所以你决定先做一道数据结构题：

给定一个长度为 $n$ 的序列 $a_1\cdots a_n$。你需要回答 $m$ 个询问，第 $i$ 个询问给定一个区间 $[l_i,r_i]$，请你求出这个区间中所有非空子集的最大公约数的乘积。由于答案可能很大，每次询问请你求出其对 $998244353$ 取模的结果。

输入格式

第一行两个正整数 $n,m$，含义同题目描述。

接下来一行 $n$ 个正整数描述序列 $a_1\cdots a_n$。

接下来 $m$ 行，第个 $i$ 行是 $l_i,r_i$，描述第 $i$ 个询问。

输出格式

输出 $m$ 行，对于每个询问输出询问答案对 $998244353$ 取模的结果。

样例数据

样例 1 输入

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

样例 1 输出

15
216
546750

样例 2 输入

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

样例 2 输出

889738671
989336054
14898500
6291
1369452
867407130

子任务

Idea：ouuan&lk，Solution：ccz181078，Code：ouuan&lk，Data：ouuan&lk

对于 $10\%$ 的数据，满足 $n,m\le10$。

对于另外 $10\%$ 的数据，满足 $n,m\le1000$。

对于另外 $20\%$ 的数据，满足 $1\le a_i\le1000$。

对于另外 $10\%$ 的数据，满足对所有 $1\le i < n$，$l_i\le l_{i+1}\le 10^5$ 且 $r_i\le r_{i+1}\le 10^5$

对于另外 $20\%$ 的数据，满足 $1\le a_i\le30000$。

对于 $100\%$ 的数据，满足 $1\le n,m,a_i\le 10^5$，$1\le l_i\le r_i\le n$。