F-函数函数函_牛客挑战赛55

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 70 M，其他语言140 M
64bit IO Format: %lld

题目描述

定义一个长度为 $n$ 的数列 $a$ 的“简单函数”（下标从 $1$ 开始）：
$F(a)=\sum_{l=1}^n\sum_{r=l}^n\max(\sum_{l\le j\le r,j\mod 2 = 1}a_j,\sum_{l\le j\le r,j\mod 2 = 0}a_j)$

显然给定一个数列对其求值太 $\text{naive}$ 了，现在我们考虑多次询问，每次询问给定一个区间 $[l,r]$ 要求你求出 $F(a[l,r])$ 的值：
$F(a[l,r]) = \sum_{pl=l}^r\sum_{pr=pl}^r\max(\sum_{pl\le j\le pr,j\mod 2 = 1}a_j,\sum_{pl\le j\le pr,j\mod 2 = 0}a_j)$

输入描述:

第一行两个整数  分别为数列  的长度和询问数。

接下来一行， 个整数，表示  。

接下来  行，每行两个整数  ，为询问区间

满足  。

输出描述:

 行，每行一个整数，为第  个询问的答案对  取模。

示例1

输入

复制

10 10
7 7 3 7 6 4 1 4 5 6 
5 6
8 9
5 7
7 7
4 8
2 5
1 8
1 8
1 10
3 5

输出

复制