Miguel și Baza 2

Cerința

Miguel a învățat cum să scrie numere în baza 2 și cum merg operațiile pe biți, așa că a inventat următorul joc:

Ai primit un șir de $N$ numere $v_1$, $v_2$, ..., $v_n$ și $Q$ interogări. Pentru fiecare interogare, ai la dispoziție două numere naturale $A$ și $B$ cu semnificația că $v_A$ devine egal cu $B$. După fiecare interogare, trebuie să afișezi numărul magic corespunzător noului șir. De menționat că după afișarea numărului magic, șirul nu revine la starea inițială.

Numărul magic al unui șir $V$ de lungime $N$ este egal cu suma tuturor numerelor din șirurile $a_1$, $a_2$, ..., $a_n$. Pentru $i=1$, $a_i$ este egal cu $V$ iar pentru fiecare $i \gt 1$, $a_i$ conține rezultatele operației pe biți AND între oricare două numere consecutive din $a_{i-1}$, păstrând ordinea relativă a perechilor. De menționat că șirul $a_i$ conține $N-i+1$ elemente.

De exemplu, dacă $V=\{1,3,5,7\}$, atunci $a_1=\{1,3,5,7\}, a_2=\{1,1,5\}, a_3=\{1,1\}, a_4=\{1\}$ iar numărul magic al lui $V$ este egal cu $(1+3+5+7)+(1+1+5)+(1+1)+(1)=26$.

Date de intrare

De pe prima linie se citesc numerele naturale $N$ și $Q$. A doua linie conține $N$ numere întregi $v_1$, $v_2$, ..., $v_n$. Pe următoarele $Q$ linii se află câte o interogare, de forma A B.

Date de ieșire

Se vor afișa cele $Q$ numere magice, dispuse pe câte o linie.

Restricții și Precizări

• $1 \leq N, Q \leq 100.000$
• $0 \leq a_i \leq 100.000$ pentru oricare $1 \leq i \leq N$
• $0 \leq B \leq 100.000$
• $1 \leq A \leq N$

Exemplu

stdin

5 4
1 5 3 7 4
5 3
2 2
3 4
1 7

stdout

35
31
24
32

Explicație

După prima interogare, șirul devine $1,5,3,7,3$ iar numărul magic este egal cu $(1+5+3+7+3)+(1+1+3+3)+(1+1+3)+(1+1)+(1)=35$. Pentru a obține $a_2$ vom efectua următoarele operații: $1\&5$, $5\&3$, $3\&7$, $7\&3$.