Diferențe pentru problema/sufle între reviziile #1 si #2

== include(page="template/taskheader" task_id="sufle") ==

Poveste și cerință...

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

h2. Date de intrare

Fișierul de intrare $sufle.in$ ...

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.

h2. Date de ieșire

În fișierul de ieșire $sufle.out$ ...

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.

h2. Restricții
* $... ≤ ... ≤ ...$

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

h2. Exemplu