Description

atm joined a mental arithmetic training class. After hard practice, he became very fast at computing logarithms base $2$, and is known as the Log Hero.

One day, the Log Hero’s friend drd has some integer sequences to transform, and the Log Hero happens to use his power.

The transformation rule is: for every integer in some chosen subarray, change it to $[\log_2(x)+1]$, where $[\ ]$ means taking the floor. That is, for each number, compute the base $2$ logarithm and then take the floor.

For example, applying the operation once to the sequence $3,4,2$ will change it into $2,3,2$.

drd needs to know, after each such operation, what the sum of the entire sequence is.

Input Format

The first line contains two positive integers $n,m$.

The second line contains $n$ numbers, representing the integer sequence, all of which are positive.

The next $m$ lines each contain two numbers $L$ and $R$, meaning that in this operation atm applies the transformation to the interval $[L,R]$. The sequence is indexed starting from $1$.

Output Format

Output $m$ lines. Each line should be the sum of the entire sequence after atm finishes one operation, in order.

3 3
5 6 4
1 2
2 3
1 3

10
8
6

Hint

For $30\%$ of the testdata, $n,m \le 10^3$.

For $100\%$ of the testdata, $n,m \le 10^5$.

Time limit: 1 second, 256M. Lanqiao Cup 2014, the 5th National Final.

The official testdata seems to be wrong. The rebuilt testdata is designed with $1 \leq a_i \leq 10^9$.

Translated by ChatGPT 5