sufle

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ță

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 descrise 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.