题目描述

33DAI 抓了 $n$ 只宝可梦，编号从 $1\sim n$，编号为 $i$ 的宝可梦能力值为 $a_i$。

现在他对这些宝可梦进行了 $m$ 次强化，第 $i$ 次对第 $l_i\sim r_i$ 只宝可梦进行了以下操作：

• 如果这只宝可梦的能力值是奇数，则能力值增加 $1$。
• 如果这只宝可梦的能力值是偶数，则能力值保持不变。

求最终的宝可梦的能力值之和。

输入格式

第一行两个整数：$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 分）：没有特殊限制。