atm參加了速算訓練班，經(jīng)過刻苦修煉，對以2為底的對數(shù)算得飛快，人稱Log大俠。

    一天，Log大俠的好友 drd 有一些整數(shù)序列需要變換，Log大俠正好施展法力...

    變換的規(guī)則是： 對其某個子序列的每個整數(shù)變?yōu)? [log_2 (x) + 1]  其中 [] 表示向下取整，就是對每個數(shù)字求以2為底的對數(shù)，然后取下整。
    例如對序列 3 4 2 操作一次后，這個序列會變成 2 3 2。
    
    drd需要知道，每次這樣操作后，序列的和是多少。

第一行兩個正整數(shù) n m 。
第二行 n 個數(shù)，表示整數(shù)序列，都是正數(shù)。
接下來 m 行，每行兩個數(shù) L R 表示 atm 這次操作的是區(qū)間 [L, R]，數(shù)列序號從1開始。

輸出 m 行，依次表示 atm 每做完一個操作后，整個序列的和。

零基礎(chǔ)同學可以先學習視頻課程，包含C/C++、Python、百練、藍橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習題，還有老師答疑，點擊這里了解課程詳情

藍橋杯