由于你不会设计哥德尔机，所以你决定先做一道数据结构题：
给定一个长度为 $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$。