#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=1e6+10;
const ll mod=(1ll<<61)-1;
const ll base=15485863;
ll cnt=0,pw[maxN];
ll lab[maxN];
map<ll,ll> mp;
void ers(ll x,ll v)
{
if(x!=0) cnt-=v*mp[mod-x];
mp[x]-=v;
}
void add(ll x,ll v)
{
if(x!=0) cnt+=v*mp[mod-x];
mp[x]+=v;
}
ll findset(ll x)
{
return lab[x]<0?x:lab[x]=findset(lab[x]);
}
ll tplt;
ll val[maxN];
void unite(ll u,ll v)
{
u=findset(u);
v=findset(v);
if(u==v)
{
return;
}
tplt--;
if(lab[u]>lab[v]) swap(u,v);
ers(val[u],-lab[u]);
ers(val[v],-lab[v]);
val[u]+=val[v];
val[u]%=mod;
lab[u]+=lab[v];
lab[v]=u;
add(val[u],-lab[u]);
}
ll n,t,p[maxN],q[maxN];
void solve()
{
cin >> n >> t;
for(int i=1;i<=n;i++)
{
cin >> p[i];
q[i]=p[i];
}
pw[0]=1;
for(int i=1;i<maxN;i++) pw[i]=pw[i-1]*base%mod;
sort(q+1,q+n+1);
tplt=n;
for(int i=1;i<=n;i++)
{
lab[i]=-1;
val[i]=pw[p[i]]-pw[q[i]];
val[i]%=mod;
if(val[i]<0) val[i]+=mod;
add(val[i],-lab[i]);
}
ll ct=0;
for(int cc=1;cc<=t;cc++)
{
ll x;
cin >> x;
if(x==1)
{
ll a,b;
cin >> a >> b;
ll i,j;
i=a;
j=b;
a=findset(a);
b=findset(b);
if(a==b) {swap(p[i],p[j]);continue;}
ers(val[a],-lab[a]);
ers(val[b],-lab[b]);
val[a]-=pw[p[i]]-pw[p[j]];
val[b]-=pw[p[j]]-pw[p[i]];
val[a]%=mod;
val[b]%=mod;
if(val[a]<0) val[a]+=mod;
if(val[b]<0) val[b]+=mod;
add(val[a],-lab[a]);
add(val[b],-lab[b]);
swap(p[j],p[i]);
}
else if(x==2)
{
ll a,b;
cin >> a >> b;
unite(a,b);
}
else if(x==4)
{
cout << cnt << '\n';
// ct++;
}
else
{
// ct++;
if(mp[0]==n) cout <<"DA\n";
else cout <<"NE\n";
}
}
}
int main()
{
fastio
//freopen(TASKNAME".INP","r",stdin);
//freopen(TASKNAME".OUT","w",stdout);
solve();
}
