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

题目描述

背景：yr非常喜欢吃大米。据yr的室友所知，他可以一天三顿都吃大米！

yr家新进了一批大米，这些大米共有 n 堆，它们整齐地一字摆放在yr家的仓库中，从左到右编号为 1,2,...,n，其中，第 i 堆大米的重量为 w_i 。特别的是，所有大米堆的重量都是奇数。
由于经常吃大米，yr学会了一项技能，他可以指定两个整数 l,r ，然后将编号为 l 到 r 的大米堆的重量做如下改变：
  • 如果 w_i 为奇数，将w_i变为原来的二倍，即：
  • 如果 w_i 为偶数，将w_i变为原来的一半，即：
yr决定执行 m 次技能，他会告诉你每次操作的区间 l,r，你需要在每次yr执行完技能后告诉他仓库中此时大米堆的总重量，即：。
如果你每次都正确回答的话，yr将会奖励你一大碗米饭。

注意：操作之间不是独立的，每次yr施放完技能后，大米堆的重量将会永久改变。

输入描述:

第一行输入两个整数  ，表示大米堆的数量和执行的操作数。
第二行输入 n 个整数  ， w_i 表示第 i 堆大米的初始重量，保证所有的 w_i 都为奇数。
接下来输入 m 行，每行两个整数 ，表示要执行的区间。

输出描述:

输出 m 行，每行一个整数，表示执行完操作后全部大米堆的总重量。
示例1

输入

复制 
5 5
1 3 5 7 9
1 3
2 4
2 5
4 4
1 3

输出

复制 
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。