题目描述
背景：yr非常喜欢吃大米。据yr的室友所知，他可以一天三顿都吃大米！
yr家新进了一批大米，这些大米共有 n 堆，它们整齐地一字摆放在yr家的仓库中，从左到右编号为 1,2,...,n，其中，第 i堆大米的重量为wi 。特别的是，所有大米堆的重量都是奇数。
由于经常吃大米，yr学会了一项技能，他可以指定两个整数 l,r ，然后将编号为 l 到 r 的大米堆的重量做如下改变：
- 如果 wi 为奇数，将iwi变为原来的二倍
- 如果 wi 为偶数，将wi变为原来的一半
如果你每次都正确回答的话，yr将会奖励你一大碗米饭。
注意：操作之间不是独立的，每次yr施放完技能后，大米堆的重量将会永久改变。
输入
第一行输入两个整数 n m (1≤n,m≤2×105) ，表示大米堆的数量和执行的操作数。
第二行输入 n 个整数 wi (1≤wi≤109) ，wi 表示第 i 堆大米的初始重量，保证所有的wi 都为奇数。
接下来输入 m行，每行两个整数 l,r (1≤l≤r≤n)，表示要执行的区间。
输出
输出 m行，每行一个整数，表示执行完操作后全部大米堆的总重量。 样例输入 Copy
5 5
1 3 5 7 9
1 3
2 4
2 5
4 4
1 3
样例输出 Copy
34
33
43
50
41
提示
最初 w 1 3 5 7 9 。
第一次操作后：w= 2 6 10 7 9 ，和为34。
第二次操作后：w= 2 3 5 14 9 ，和为33。
第三次操作后：w= 2 6 10 7 18 ，和为43。
第四次操作后：w= 2 6 10 14 18 ，和为50。
第五次操作后：w=1 3 5 14 18 ，和为41。