#P12524. [Aboi Round 1] I なんです

[Aboi Round 1] I なんです

题目背景

题目描述

有一个长度为 nn 的序列 {a}\{a\}qq 次询问,每次给你一个区间 [l,r][l,r],求该区间内所有长度为奇数的子序列的 gcd\gcd 的平方之积,答案对 998244353998244353 取模。

输入格式

第一行两个正整数 n,qn,q

第二行 nn 个正整数 aia_i

之后 qq 行,每行两个正整数 l,rl,r

输出格式

对于每次询问,输出对应的答案。

10 5
1 3 5 2 4 6 8 8 8 10
1 3
5 7
3 6
8 10
7 10
225
147456
230400
1638400
562036629
10 5
2 2 2 2 2 2 2 2 2 2
1 2
1 4
1 5
1 6
1 7
16
65536
301989884
932051910
299560064

提示

对于 100%100\% 的数据,1n,q,ai1051\leq n,q,a_i\leq10^5

本题采用捆绑测试,你需要通过一个子任务的所有测试点才能得到该子任务的分数。

子任务编号 nn qq aia_i 特殊性质 分值
11 20\le20 105\le10^5 / 1010
22 103\le10^3
33 3×104\le3\times10^4
44 105\le10^5 A\text{A} 55
55 300\le300 / 1010
66 105\le10^5 5555

特殊性质 A\text{A}:所有 aia_i 均相同。