Sufle este un personaj cu urechi ascuțite, îndrăgostit de algoritmică. El are o antipatie profundă față de Aisimok, cel care îl tot provoacă să rezolve probleme folosind tot felul de formule. Sufle a botezat aceste probleme Emsiteanap. Astăzi Aisimok i-a aruncat tânărului Sufle o nouă provocare:

Pentru oricare două numere naturale se definește următoarea operație:

• se consideră reprezentările în baza 2 pentru cele două numere;
• se alege o poziție în reprezentarea binară a primului număr;
• se schimbă cifra situată pe acea poziție în primul număr cu cifra aflată pe exact aceeași
  poziție în al doilea număr. (Observați cum Aisimok, obsedat de matematică, nu a folosit termenul bit, tocmai pentru a-l irita pe Sufle.)

Pentru un șir oarecare de numere naturale, se poate aplica de oricâte ori și asupra oricăror două numere operația descrisă mai sus. Scopul final este ca suma pătratelor numerelor din șir să ajungă la valoarea minim posibilă. Denumim costul șirului acestă valoare minimă.

Pentru a deveni și mai antipatic, Aisimok îi cere lui Sufle să calculeze aceast cost pentru mai multe subsecvențe ale unui șir dat. Costul unei subsecvențe este egal cu costul șirului definitit de subsecvența dată.

Cerința

Pentru un șir cunoscut și pentru mai multe subsecvențe date să se calculeze suma minimă a pătratelor numerelor din subsecvență după aplicare a operației descrise, de oricâte ori se consideră necesar și asupra oricăror numere din subsecvență.

Date de intrare

Fișierul sufle.in conține pe prima linie numerele natural N și Q, reprezentând numărul de termeni din șir respective numărul de interogări. A doua linie conține N numere naturale, termenii șirului. Pe următoarele Q linii sunt descries interogările. Fiecare dintre aceste linii va conține câte două numere natural L și R capetele subsecvenței corespunzătoare unei interogări.

Date de ieșire

Fişierul sufle.out va conţine Q linii. Pe fiecare dintre aceste linii se va afişa câte un număr, reprezentând răspunsul la interogarea corespunzătoare din fişierul de intrare.

Restricții și precizări

• 1 ≤ N ≤ 100 000
• 1 ≤ Q ≤ 100.000
• 1 ≤ L ≤ R ≤ N
• Pentru toate interogările se va considera că operaţiile se vor aplica pe şirul iniţial, fără a ţine cont de modificările rezultate din alte interogări precedente.
• Toţi termenii din şir sunt numere naturale mai mici sau egale cu 1.000.000.

Exemplu:

sufle.in

6 2
8 10 5 6 0 5
2 5
1 1

sufle.out

125
64

Explicație

Se solicită răspunsul pentru două interogări:

Pentru prima interogare numerele din subsecvenţă sunt 10, 5, 6 şi 0 care au reprezentările binare 1010, 101, 110, 0.

Vom numerota poziţiile începând cu 1 care corespunde ultimei cifre crescător spre cea mai semnificativă cifră.

Aplic operaţia pentru al doilea şi al patrulea număr pentru poziţia 1. Obţin numerele 1010,100,110,1.

Aplic operaţia pentru primul şi ultimul număr la poziţia 2. Obţin numerele 1000, 100, 110, 11.

Numerele în baza zece sunt 8, 4, 6, 3. Suma pătratelor 125 este minimă. Nu se poate obţine o sumă mai mică.

La a doua interogare secvenţa conţine doar numărul 8 deci nu se poate aplica niciodată operaţia. Suma pătratelor se reduce la un singur număr, pătratul lui 8 care este 64.