前情回顾:
定义一个数组的权值和为:假设数组乘积为S,数组的权值和为使得x*y=S的所有(x,y)对数(x, y均为正整数) 给你一个数组A,请你求出他的所有非空子序列的权值和,由于答案可能很大,请对998244353取模 例如S=2, 那么就有2对(x, y)符合要求, 分别为(1, 2), (2, 1)
现在小L希望知道某个子数组的权值和,但是他不会做,所以他来询问你了,你能帮帮他吗? 子数组是数组的一段连续区间,例如是数组的子数组
第一行两个个整数,代表数组大小和询问个数 第二行个整数,表示给定的数组 接下来行,每行两个整数代表询问的区间
对于每个询问,输出一个整数,表示答案
输入样例1
2 1 1 2 1 2
输出样例1
5
保证所有均为1或质数