题目描述

唐僧师徒途经火焰山，烈火挡路，孙悟空去借芭蕉扇。铁扇公主说芭蕉扇被一串符咒封印，封印上刻着一个长度为 n 的整数序列 a1, a2, ..., an。她会给你 q 次询问，每次给出两个参数 l 和 r，你需要计算并输出下面这个和：

1 * a[l] + 2 * a[l+1] + 3 * a[l+2] + ... + (r - l + 1) * a[r]

如果答案很大，只需输出对模数 998244353 取模后的结果。若你能对每个询问算出正确结果，便可解开封印，借到芭蕉扇通过火焰山。

输入格式

第一行两个整数n,q(1≤n,q≤1e5)

第二行n个整数a1∼an(1≤ai≤1e9)

接下来q行，每行两个整数l,r(1≤l≤r≤n)，表示q组询问。

输出格式

输出q行，表示对于每次询问的答案。

样例

3 1
3 2 1
2 3

4

Limitation

1s, 1024KiB for each test case.