teams

„Este nevoie de un rând întreg pentru a construi liniștea și de o singură actualizare pentru a o distruge.”

Gigel, un manager de top, este responsabil cu formarea echipelor pentru ONI (Olimpiada Națională de Improvizații).

La concurs participă $N$ elevi, așezați în rând și indexați de la $1$ la $N$. Pentru a evalua dinamica echipelor, Gigel a creat un „profil de personalitate” pentru fiecare elev, reprezentat printr-un număr natural stocat în vectorul $v$.

Secretul acestui profil constă în faptul că fiecare bit din reprezentarea binară a lui $v[i]$ semnifică o anumită preferință sau trăsătură a elevului $i$ (de exemplu: dacă preferă indexarea vectorilor de la $1$ în loc de $0$, dacă pune acolada { pe același rând cu if-ul în loc de rândul următor, sau dacă abuzează de #pragma-uri etc.).

Concurenții pot participa fie singuri, fie în echipe de câte $2$. Pentru a forma echipele, Gigel alege o subsecvență continuă din rândul de elevi. Apoi, el își imaginează această subsecvență ca pe o bandă flexibilă pe care o pliază exact la jumătate. Elevii care, în urma acestei plieri, ajung să stea față în față (să se suprapună), vor deveni coechipieri. În cazul în care subsecvența selectată are un număr impar de elevi, cel aflat exact pe cuta de pliere nu se va suprapune cu nimeni și va participa singur.

Gigel știe că, într-o echipă de $2$, pentru fiecare trăsătură la care cei doi membri au opinii diferite (unul are bitul $1$, iar celălalt $0$), va apărea o discuție în contradictoriu. Astfel, el deduce că tensiunea unei echipe este exact rezultatul operației sau exclusiv pe biți ($\oplus$) dintre profilurile celor doi coechipieri. Un elev care participă singur nu are cu cine să se contrazică, deci tensiunea echipei sale este implicit $0$ (echivalentul matematic al operației $x \oplus x = 0$).

Definim echilibrul unei subsecvențe, notat cu $\text{echilibru}(i, j)$, ca fiind suma tensiunilor tuturor echipelor formate în acea subsecvență.

Cerință

Luându-și foarte în serios rolul de selecționer, Gigel vă cere să rezolvați următoarele două sarcini:

1. Să calculați suma echilibrelor pentru toate subsecvențele continue posibile din șirul inițial. Mai exact, se cere calcularea valorii:

$\displaystyle \sum_{i=1}^{N} \sum_{j=i}^{N} \text{echilibru}(i, j) \pmod{10^9 + 7}$

2. Să evaluați $Q$ scenarii de mutări tactice, date sub forma $(poz, val)$: „Dacă l-aș scoate temporar din lot pe elevul de pe poziția $poz$ și l-aș înlocui cu o rezervă având profilul de personalitate egal cu $val$, care ar fi noua sumă totală a echilibrelor modulo $10^9 + 7$?”.

Notă: Nu vă faceți griji, aceste înlocuiri sunt doar simulări pe foaie. După fiecare interogare, elevul original își recapătă locul, iar șirul revine la starea inițială.

Date de intrare

Fișierul de intrare teams.in conține pe prima linie numerele naturale $N$ și $Q$, reprezentând numărul total de elevi și numărul de scenarii pe care trebuie să le rezolvăm. Pe cea de-a doua linie se găsesc $N$ numere naturale, separate prin câte un spațiu, reprezentând profilurile de personalitate ale elevilor (elementele vectorului $v$). Pe fiecare dintre următoarele $Q$ linii este descris câte un scenariu, exact ca mai sus.

Date de ieșire

Fișierul de ieșire teams.out va conține pe prima linie un singur număr natural, reprezentând suma echilibrelor pentru toate subsecvențele continue posibile din rândul elevilor, calculată modulo $10^9 + 7$. Fiecare dintre următoarele $Q$ linii va conține răspunsul modulo $10^9 + 7$ la fiecare scenariu în parte, în ordinea în care acestea au fost citite.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$
• $0 \leq Q \leq 100 \ 000$
• $0 \leq v[i] < 2^{31}$
• $1 \leq poz \leq N$
• $0 \leq val < 2^{31}$
• Restricțiile asupra lui $v[i]$ sunt valabile pentru orice $1 \leq i \leq N$.
• Notă: Operația sau-exclusiv (XOR) pe biți este reprezentată în C/C++ prin operatorul ^.

Exemplul 1

teams.in

4 0
1 2 1 3

teams.out

14

Explicație

În primul exemplu, dacă am alege întregul șir, atunci coechipieri ar fi elevii aflați pe pozițiile $(1, 4)$ și $(2, 3)$. Așadar, echilibrul subsecvenței $(1, 4)$ este $(1 \oplus 3) + (2 \oplus 1) = 2 + 3 = 5$. Pentru celelalte subsecvențe se procedează similar, echilibrele fiind, în ordinea lexicografică a capetelor: $0$, $3$, $0$, $5$, $0$, $3$, $1$, $0$, $2$, $0$. Observăm că suma lor este exact $14$.

Exemplul 2

teams.in

10 7
45 12 107 88 3 56 120 77 21 99
3 64
1 8
10 127
5 0
7 56
1 45
8 33

teams.out

6623
6508
6580
6603
6584
6495
6623
6555