#include <iostream>
#include <chrono>
#include <random>
#include <map>
#include <algorithm>
using namespace std;
using ll=long long;
const int MN=1e6+13;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
//mt19937_64 rng(0);
ll mp[MN];
int N, Q;
int A[MN], B[MN];
int dsu[MN]; ll sz[MN];
ll res[MN], cor[MN];
map<ll, ll> cnt1, cnt2;
ll ans;
ll get(ll x) { return x*(x-1)/2; }
ll contribution(ll x) { return cnt1[x]*cnt1[x]-cnt2[x]; }
int find(int x)
{
if (dsu[x]==x) return x;
else return dsu[x]=find(dsu[x]);
}
bool unite(int x, int y)
{
x=find(x); y=find(y);
if (x==y) return 0;
//cerr<<"UNITE "<<x<<' '<<y<<endl;
//cerr<<(res[x]^cor[x])<<' '<<(res[y]^cor[y])<<": "<<ans<<endl;
if (res[x]^cor[x]) ans-=contribution(res[x]^cor[x]);
cnt1[res[x]^cor[x]]-=sz[x];
cnt2[res[x]^cor[x]]-=sz[x]*sz[x];
if (res[x]^cor[x]) ans+=contribution(res[x]^cor[x]);
if (res[y]^cor[y]) ans-=contribution(res[y]^cor[y]);
cnt1[res[y]^cor[y]]-=sz[y];
cnt2[res[y]^cor[y]]-=sz[y]*sz[y];
if (res[y]^cor[y]) ans+=contribution(res[y]^cor[y]);
dsu[y]=x; sz[x]+=sz[y];
res[x]^=res[y]; cor[x]^=cor[y];
if (res[x]^cor[x]) ans-=contribution(res[x]^cor[x]);
cnt1[res[x]^cor[x]]+=sz[x];
cnt2[res[x]^cor[x]]+=sz[x]*sz[x];
if (res[x]^cor[x]) ans+=contribution(res[x]^cor[x]);
//cerr<<(res[x]^cor[x])<<": "<<ans<<endl;
return 1;
}
int main()
{
for (int i=0; i<MN; i++) mp[i]=rng();
cin>>N>>Q;
for (int i=1; i<=N; i++)
{
cin>>A[i];
B[i]=A[i];
}
sort(B+1, B+1+N);
for (int i=1; i<=N; i++)
{
dsu[i]=i; sz[i]=1;
res[i]=mp[A[i]];
cor[i]=mp[B[i]];
cnt1[res[i]^cor[i]]++;
cnt2[res[i]^cor[i]]++;
}
for (auto [x, y]:cnt1) if (x) ans+=contribution(x);
while (Q--)
{
int T; cin>>T;
if (T==1)
{
int x, y; cin>>x>>y;
int rx=find(x), ry=find(y);
if (res[rx]^cor[rx]) ans-=contribution(res[rx]^cor[rx]);
cnt1[res[rx]^cor[rx]]-=sz[rx];
cnt2[res[rx]^cor[rx]]-=sz[rx]*sz[rx];
if (res[rx]^cor[rx]) ans+=contribution(res[rx]^cor[rx]);
if (res[ry]^cor[ry]) ans-=contribution(res[ry]^cor[ry]);
cnt1[res[ry]^cor[ry]]-=sz[ry];
cnt2[res[ry]^cor[ry]]-=sz[ry]*sz[ry];
if (res[ry]^cor[ry]) ans+=contribution(res[ry]^cor[ry]);
res[rx]^=mp[A[x]];
res[ry]^=mp[A[y]];
swap(A[x], A[y]);
res[rx]^=mp[A[x]];
res[ry]^=mp[A[y]];
if (res[rx]^cor[rx]) ans-=contribution(res[rx]^cor[rx]);
cnt1[res[rx]^cor[rx]]+=sz[rx];
cnt2[res[rx]^cor[rx]]+=sz[rx]*sz[rx];
if (res[rx]^cor[rx]) ans+=contribution(res[rx]^cor[rx]);
if (res[ry]^cor[ry]) ans-=contribution(res[ry]^cor[ry]);
cnt1[res[ry]^cor[ry]]+=sz[ry];
cnt2[res[ry]^cor[ry]]+=sz[ry]*sz[ry];
if (res[ry]^cor[ry]) ans+=contribution(res[ry]^cor[ry]);
}
else if (T==2)
{
int x, y; cin>>x>>y;
unite(x, y);
}
else if (T==3)
{
if (cnt1[0]==N) cout<<"DA"<<endl;
else cout<<"NE"<<endl;
}
else cout<<ans/2<<endl;
}
return 0;
}
