Shuffle

Se dau două numere naturale $N$ și $Q$.

Se va genera un șir de numere $A_0,A_1,\ldots,A_{2^N-1}$ după următorii pași:

• Inițial, $A_i=i$, pentru fiecare $0 \le i < 2^N$.
• Apoi, pentru fiecare $K$ de la $1$ la $N$, se împarte șirul în subsecvențe disjuncte de lungime $2^K$, iar fiecare dintre aceste subsecvențe va fi oglindită.

De exemplu, pentru $N=4$, șirul $A$ va fi generat în felul următor:

• Inițial, $A=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]$.
• După $K=1$: $A=[\underline{1,0},\underline{3,2},\underline{5,4},\underline{7,6},\underline{9,8},\underline{11,10},\underline{13,12},\underline{15,14}]$.
• După $K=2$: $A=[\underline{2,3,0,1},\underline{6,7,4,5},\underline{10,11,8,9},\underline{14,15,12,13}]$.
• După $K=3$: $A=[\underline{5,4,7,6,1,0,3,2},\underline{13,12,15,14,9,8,11,10}]$.
• După $K=4$: $A=[\underline{10,11,8,9,14,15,12,13,2,3,0,1,6,7,4,5}]$.

Cerință

Va trebui să răspundeți la $Q$ interogări de următorul fel:

• $\text{L R}$: Care este valoarea sumei $A_L+A_{L+1}+\ldots+A_R$?

Date de intrare

Pe prima linie se vor afla două numere $N$ și $Q$, cu semnificațiile din enunț,

Pe fiecare dintre următoarele $Q$ linii se vor afla câte două numere $L_i$ și $R_i$, capetele celor $Q$ interogări.

Date de ieșire

Pentru fiecare interogare $(L_i,R_i)$, afișați valoarea sumei $A_L+A_{L+1}+\ldots+A_R$.

Restricții și precizări

• $1 \leq N \leq 30$;
• $1 \leq Q \leq 200 \ 000$
• $0 \le L_i \le R_i < 2^N$, pentru fiecare $1 \le i \le Q$

Exemplu

stdin

4 7
0 15
0 7
8 15
3 13
14 14
6 7
6 9

stdout

120
92
28
82
4
25
30

Explicație

Pentru prima interogare, $A_0+A_1+\ldots+A_{15}=\frac{15 \cdot 16}{2}=120$.
Pentru a doua interogare, $A_0+A_1+\ldots+A_{7}=8+9+\ldots+15=92$.
Pentru a treia interogare, $A_8+A_9+\ldots+A_{15}=0+1+\ldots+7=28$.
Pentru a patra interogare, $A_3+A_4+\ldots+A_{13}=9+14+15+12+13+2+3+0+1+6+7=82$.