K – Ragdoll

https://codeforces.com/gym/102832/problem/K

Once there was a lovely ragdoll cat, named Little Zara, who liked trees and math. One day she met the doge Adam. Adam had just planted some trees each consisting of only one node. The nodes were numbered from 11 to nn, and the ii-th node was assigned a value aiai. Adam liked pairing tree nodes, but he disliked some node pairs. A pair of nodes (i,j)(i,j) was considered bad if ii and jj were in the same tree and gcd(ai,aj)=ai⊕ajgcd⁡(ai,aj)=ai⊕aj, where gcd(x,y)gcd⁡(x,y) denotes the greatest common divisor (GCD) of integers xx and yy, and ⊕⊕ denotes the bitwise XOR operation. Adam wondered how many bad pairs there were in his forest.

Zara was good at solving problems about trees and math, so she could answer Adam’s question in a short time. However, Adam was so naughty a dog that he would repeatedly change the forest slightly and ask Zara his question again after the change.

The changes Adam might make are listed here:

1. Adam plants a new tree with only one node numbered xx and assigned a value vv.
2. Adam uses magic to merge the tree containing the node xx and the one containing the node yy. If xx and yy are in the same tree before the operation, the magic fails and has no effect.
3. Adam changes the value of node xx to vv.

Now you are expected to help Zara answer all questions Adam asked, in order that they could sing and dance together happily.

Input

The first line contains two integers nn and mm (1≤n≤1051≤n≤105, 1≤m≤2×1051≤m≤2×105), representing the number of nodes in the original forest and the number of changes Adam would make, respectively.

The next line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤2×1051≤ai≤2×105).

Each of the next mm lines describes a change Adam made, starting with an integer tt (1≤t≤31≤t≤3) representing the type of the change.

• If t=1t=1, it will be followed by two integers xx and vv (n<x≤n+mn<x≤n+m, 1≤v≤2×1051≤v≤2×105). It is guaranteed that xx’s are distinct in all changes of the first type.
• If t=2t=2, it will be followed by two integers xx and yy (1≤x,y≤n+m1≤x,y≤n+m). It is guaranteed that the node xx and yy already exist in the forest.
• If t=3t=3, it will be followed by two integers xx and vv. (1≤x≤n+m1≤x≤n+m, 1≤v≤2×1051≤v≤2×105). It is guaranteed that the node xx already exists in the forest.

Output

For each change Adam made, print one line with a single integer, representing the number of bad pairs in the forest after the change.

Examples

Input

3 6
3 2 1
2 1 2
1 5 3
2 1 2
2 3 2
2 5 1
3 3 2

Output

1
1
1
1
2
4

Input

10 6
6 6 4 7 7 4 6 4 6 5
2 5 1
2 10 7
2 8 7
2 7 2
2 6 2
2 9 1

Output

1
1
3
4
7
8

代码：

#include<bits/stdc++.h>
#define ls l,mid,rt<<1
#define rs mid+1,r,rt<<1|1
#define endl '\n'
#define ps puts("###")
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int MAXN = 1e6+10;
const double EPS = 1e-12;
const ll mod = 1e9+7;
vector<ll>q[MAXN];
ll n,m,t,s;
ll a[MAXN];
ll fa[MAXN];
ll num[MAXN];
unordered_map<ll,ll>f[MAXN];
int fin(int x)
{
    if(fa[x]==x)
        return x;
    fa[x]=fin(fa[x]);
    return fa[x];
}
void un(int x,int y)
{
    ll p1=fin(x),p2=fin(y);
    fa[p1]=p2;
    //cout<<p1<<" "<<p2<<endl;
    for(auto i:f[p1])
    {
        ll id=i.first;
        //cout<<id<<endl;
        for(int k=0;k<q[id].size();k++)
        {
            ll u=q[id][k];
            //cout<<u<<endl;
            if(f[p2].count(u))//删了就T不知道为什么
            s+=i.second*f[p2][u];
            //cout<<s<<endl;
        }
    }
    for(auto i:f[p1])
    {
        ll id=i.first;
        f[p2][id]+=i.second;
    }
    f[p1].clear();
    num[p2]+=num[p1];
    return;
}
int main()
{
    scanf("%lld %lld",&n,&m);
    for(int i=1;i<=200000;i++)
    {
        for(int j=i+i;j<=200000;j+=i)
        {
            if((j^(j-i))==i)
            {
                q[j].push_back(i^j);
                q[i^j].push_back(j);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        f[i][a[i]]=1;
        fa[i]=i;
        num[i]=1;
    }
    s=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%lld",&t);
        if(t==1)
        {
            ll x,v;
            scanf("%lld %lld",&x,&v);
            a[x]=v;
            fa[x]=x;
            f[x][v]=1;
            num[x]=1;
            printf("%lld\n",s);
        }
        else if(t==2)
        {
            ll x,y;
            scanf("%lld %lld",&x,&y);
            ll p1,p2;
            p1=fin(x);
            p2=fin(y);
            if(p1!=p2)
            {
                if(num[p1]<num[p2])
                un(p1,p2);
                else
                un(p2,p1);
            }

            printf("%lld\n",s);
        }
        else if(t==3)
        {
            ll x,v;
            scanf("%lld %lld",&x,&v);
            for(int k=0;k<q[a[x]].size();k++)
            {
                ll u=q[a[x]][k];
                s-=f[fa[x]][u];
            }
            f[fa[x]][a[x]]--;
            a[x]=v;
            //cout<<s<<endl;
            for(int k=0;k<q[a[x]].size();k++)
            {
                ll u=q[a[x]][k];
                s+=f[fa[x]][u];
            }
            f[fa[x]][a[x]]++;
            printf("%lld\n",s);
        }
    }
}