该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

上图中的每个圆点是“桦加沙”台风的不同监测序列点，现在D老师拿到一组测试点序列值，序号从 $1\sim n$，编号为 $i$ 的值为 $a_i$。，为了更好的调试他的台风监测系统2.0 beta版，他想对这个序列进行 $m$ 次调整操作：

• 如果$l_i$至$r_i$区间某个$a_i$值是奇数，则$a_i$值增加 $1$。
• 如果$l_i$至$r_i$区间某个$a_i$值是偶数，则$a_i$值保持不变。

求经过$m$次操作后，最终这组序列值之和。

输入格式

第一行两个整数：$n,m$。

第二行为空格隔开的 $n$ 个正整数：$a_1\sim a_n$。

接下来 $m$ 行，第 $i$ 行为空格隔开的整数 $l_i,r_i$。

输出格式

输出最终序列值之和。

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

40

样例解释

• 初始测试数列：1 2 3 4 5 6 7 8
• 1 4 区间修改后：(2 2 4 4) 5 6 7 8
• 3 5 区间修改后：2 2 (4 4 6) 6 7 8
• 7 7 区间修改后：2 2 4 4 6 6 (8) 8

最终数列答案为：$2+2+4+4+6+6+8+8=40$

数据规模与约定

对于 $100\%$ 的数据，$1 \le n,m\le 10^5$，$1\le a_i\le 10^9$，$1\le l_i\le r_i\le n$。

• 子任务 1（30 分）：保证 $1\le n,m\le 1000$。
• 子任务 2（30 分）：保证 $l_i=r_i$。
• 子任务 3（40 分）：没有特殊限制。