题解思路

1. 前缀和与二次前缀和

• 令
  $P[i]=\sum_{j=1}^{i}a_j$
  （一维前缀和），
  $Q[i]=\sum_{j=1}^{i}P[j]$
  （前缀和的前缀和）。
• 则任意长度为 $x$ 的子数组和的总和
  

题目内容

$Tk$ 有一个长度为 $n$ 的数组 $a$，$Tk$ 定义 $g(x) = \sum_{i=1}^{n-x+1} \sum_{j=i}^{i+x-1} a_j$，即所有区间长度为 $x$ 的区间和，$Tk$ 会向你询问 $m$ 次，每一次给你个区间 $[l, r]$，你需要求出区间内所有素数 $y$ 对应 $g(y)$ 的和，由于所求值可能比较大，你只需要告诉他答案对 $998244353$ 的取模结果即可。

输入描述

第一行输入两个正整数 $n,m(1\leq n\leq 10^4,1\leq m\leq 2*10^5)$ 表示数组大小和 $Tk$ 的询问次数。

第二行输入 $n$ 个正整数 $a_i(1\leq a_i\leq 10^9)$ 表示数组第 $i$ 个位置的值。

接下来 $m$ 行每一行给出两个整数 $l_i,r_i(1\leq l_i\leq r_i\leq n)$ 表示 $Tk$ 第 $i$ 次询问的区间。

输出描述

输出分 $m$ 行，每一行对 $Tk$ 的询问作出回答。

示例1

输入

5 3
1 4 2 7 4
4 4
2 3
1 5

输出

0
64
82

说明

我们可以得到 $g(1)=18,g(2)=31,g(3)=33,g(4)=31,g(5)=18$

区间 $[4,4]$ 中，没有素数，所以 $g(4)=0$

区间 $[2,3]$ 中，$2$ 和 $3$ 都是素数，$g(2)+g(3)=31+33=64$

区间 $[1,5]$ 中，$2,3,5$ 是素数，$g(2)+g(3)+g(5)=31+33+18=82$