612. C Full

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define pb push_back
#define mp make_pair

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
#pragma GCC target("avx,avx2")

constexpr int INF = (int)1e9;
constexpr int N = (int)1e3 + 11;
constexpr int MAXN = (int)2e6 + 11;
constexpr int md = (int)1e9+7;

void add(int& a,int b){
    a += b;
    if(a >= md) a -= md;
}
void sub(int& a,int b){
    a -= b;
    if(a < 0) a += md;
}

int pw[MAXN];
int cnt[MAXN];
int sum[MAXN];
int subs[MAXN];
bool prime[MAXN];
int mobious[MAXN];
int lw[MAXN];
int c[MAXN];
bool used[MAXN];
int answer = 0;
vector<pair<int,int>> PrimeDivs;
//vector<int> divs[MAXN];

void rec(int pos,int t,vector<int>& v){
    if(pos == PrimeDivs.size()){
        v.pb(t);
        return;
    }
    rec(pos+1,t,v);
    for(int i = 0; i < PrimeDivs[pos].second; i++){
        t *= PrimeDivs[pos].first;
        rec(pos+1,t,v);
    }
    return;
}

vector<int> getDivs(int x){
//    if(!divs[x].empty())
//        return;
    map<int,int> cnt;
    int t = x;
    while(t > 1){
        cnt[lw[t]]++;
        t /= lw[t];
    }
    PrimeDivs.clear();
    for(auto& x : cnt)
        PrimeDivs.pb(x);
    vector<int> v;
    rec(0,1,v);
    return v;
}

void updateC(int x){
    if(used[x])
        return;
    vector<int> divs = getDivs(x);
    for(auto& j : divs){
//        cout << "div " << x << " " << j << "\n";
        c[x] += j*mobious[x/j];
    }
//    cerr << "C " << x << " " << c[x] << "\n";
    used[x] = true;
    return;
}

void ADD(int a){
    vector<int> divs = getDivs(a);
    for(auto& i : divs){
        int x = i;
//        cerr << "div " << a << " " << x << "\n";
        updateC(x);
        add(answer,c[x]*pw[cnt[x]]%md);
        cnt[x]++;
    }
}

void DEL(int a){
    vector<int> divs = getDivs(a);
    for(auto& i : divs){
        int x = i;
        updateC(x);
        cnt[x]--;
        sub(answer,c[x]*pw[cnt[x]]%md);
    }
}

void solve(){
    pw[0] = 1;
    pw[1] = 2;
    for(int i = 2; i < MAXN; i++){
        pw[i] = (pw[i-1]*2)%md;
    }
    mobious[1] = 1;
    for(int i = 2; i < MAXN; i++)
        prime[i] = 1, mobious[i] = 1, lw[i] = INF;
    for(int i = 2; i < MAXN; i++){
        if(!prime[i])
            continue;
        lw[i] = i;
        for(int j = i+i; j < MAXN; j+=i){
            lw[j] = min(lw[j],i);
            prime[j] = false;
        }
    }

    for(int i = 2; i < MAXN; i++){
        int t = i;
        int p = 0;
        set<int> st;
        while(t > 1){
//            cerr << t << "\n";
            if(st.count(lw[t])){
                mobious[i] = 0;
                break;
            }
            st.insert(lw[t]);
            t /= lw[t];
            p ^= 1;
        }
//        rec(i,0);
        if(mobious[i] == 0)
            continue;
        if(p == 0)
            mobious[i] = 1;
        else
            mobious[i] = -1;
    }

//    for(int i = 1; i < 10; i++)
//        cerr << mobious[i] << "\n";
//    return;

//    for(int i = 1; i < MAXN; i++){
//
//    }

//    getDivs(1);
//    for(auto& x : divs[1])
//        cout << x << " ";
//
//    return;

    int n,q;
    cin >> n >> q;

    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        ADD(a);
    }
    cout << answer << "\n";
    while(q--){
        int tp,x;
        cin >> tp >> x;
        if(tp == 2)
            DEL(x);
        else
            ADD(x);
        cout << answer << "\n";
    }

    return;
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int tests = 1;
//    cin >> tests;
    while(tests--){
        solve();
    }
}
/**

1 -1 -1 0 -1 1 -1 0 0

d[1] d[2] d[3] d[4] d[5] d[6] d[7] d[8] d[9] d[10] d[11]

1*(d[1]-d[2]-d[3]-d[5]+d[6]-d[7])
2*(d[2]-d[4]-d[6]-d[10]+d[12]-d[14])

3*(d[3]-d[6]-d[9]-d[15]+d[18]-d[21])
4*(d[

(pw[i-1]-1)*c[i]
(pw[i]-1)*c[i]
c[i]*(pw[i]-1-(pw[i-1]-1)) = c[i]*(pw[i]-1-pw[i-1]+1) = c[i]*(pw[i]-pw[i-1]) = c[i]*pw[i-1]

**/