题目描述

给定一个长度为 $n$ 的序列 $a_1,a_2,\ldots,a_n$。

有 $q$ 次询问，每次询问给定一个区间 $[l,r]$。你需要求出

$$\sum\limits_{i=l}^r \sum\limits_{j=i}^r (a_i+a_{i+1}+\ldots+a_j) $$

形式化的说：即求出子数组的所有子数组的和。

输入格式

第一行输入两个数 $n$ 和 $q$。

接下来一行输入 $n$ 个正整数为 $a_1,a_2,\ldots,a_n$。

接下来 $q$ 行，每行输入两个整数 $l,r$。

输出格式

一行 $n$ 个数，为 $1 \sim n$。

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

24
44
74
3

数据规模与约定

对于 $100\%$ 的数据，保证 $1\leq n,q\leq 3\times 10^5$，$1\leq a_i\leq 100$。保证 $1\leq l\leq r\leq n$。

• 子任务 1（30 分）：保证 $n,m\leq 300$。
• 子任务 2（30 分）：保证 $n,m\leq 3000$。
• 子任务 3（40 分）：没有特殊限制。