Problem 2017: Gya-chan and the gcd operation

"Memories don't live like people do. They always 'member you"

Se dau doi vectori $A$ și $B$ , ambii cu $N$ elemente, și definiția următoarei funcții:

long long f(int A[], int B[], int n){
    long long sum = 0;
    for(int i = 1; i <= n; i++)
        for(int j = i+1; j <= n; j++)
            if(B[i] == B[j]) sum += __gcd(A[i], A[j]);
    return sum;
}

Gya-chan, fiind foarte nerăbdătoare să își deschidă cadourile, se trezește în toiul nopții cu speranța să le găsească deja sub brad. Surpriză mare când în drum spre brad dă peste chiar unicul și preaiubitul Moș Crăciun. Acesta, supărat că a fost prins, decide să-i dea fetei o provocare.

Cerință

Moș Crăciun îi pune fetei $Q$ întrebări de forma $(a, b)$ , iar fata trebuie să spună care este valoarea returnată de funcția $f$ dacă se va înlocui $B_a$ cu $b$ . Actualizările lui Moș Crăciun sunt permanente, cu alte cuvinte, după fiecare operație, modificările aduse vectorului $B$ se vor păstra.

Date de intrare

Pe prima linie se află două numere, $N$ , reprezentând numărul de elemente din cei doi vectori, și $Q$ , numărul de întrebări. Pe următoarele două linii se află câte $N$ numere, prima linie conținând elementele din vectorul $A$ , iar a doua din vectorul $B$ . Pe ultimele $Q$ linii se află întrebările puse de Moș Crăciun.

Date de ieșire

Se vor afișa $Q + 1$ linii, prima desemnând valoarea inițială a funcției, iar pe următoarele $Q$ linii sunt răspunsurile după fiecare modificare.

Restricții și precizări

$1 \leq N, Q \leq 2 \cdot 10^5$
$1 \leq A_i \leq 3 \cdot 10^5$ , $1 \leq i \leq N$
$1 \leq B_i \leq N$ după fiecare operație

Bahoi vrea să bulănească problema, dar este complet interzis!!! Numărul de elemente distincte ale vectorului

B

este

\leq BULAN

. NU Primiți 5 puncte dacă ghiciți valoarea

BULAN

#	Punctaj	Restricții
1	13	$1 \leq N \leq 10$
2	12	$1 \leq A_i \leq 100$ , $1 \leq i \leq N$
3	19	$1 \leq N \leq 1\ 000$
4	25	$1 \leq N \leq 10^5$
5	31	Fără restricții suplimentare

Exemplul 1

stdin

stdout

1
4
2

Explicație

Înainte de prima modificare, valoarea returnată de funcția $f$ va fi $\gcd(2,3) = 1$ .
După prima modificare, valoarea returnată va fi $\gcd(2,2) + \gcd(2,3) + \gcd(2,3) = 2 + 1 + 1 = 4$ .

Exemplul 2