题目描述

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

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

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

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

输入格式

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

第二行为空格隔开的 $n$ 个正整数：$a_1, a_2, \dots, 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$。

数据范围与提示

• 子任务 1（30 分）：$1 \le n, m \le 1000$。
• 子任务 2（30 分）：$l_i = r_i$。
• 子任务 3（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$。