#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define dec(x, y) fixed << setprecision((y)) << (x)
#define xx first
#define yy second
#define srt(v) sort((v).begin(), (v).end())
#define srtr(v) sort((v).rbegin(), (v).rend())
#define pb push_back
#define popb pop_back
#define sz(a) (int)(a).size()
#define len(a) (int)(a).length()
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int maxn=(int)1e6+2;
const ll mod=(ll)1e9+7LL;
const int k=(ll)1e7+19LL;
int n, q, rod[maxn], h[maxn], kolko;
ll p[maxn], kon[maxn];
ll hes[maxn], hesk[maxn];
ll hesd[maxn], heskd[maxn];
set<int> s;
map<ll, set<int>> cnt;
int par(int x) {
if(rod[x]==x) return x;
return rod[x]=par(rod[x]);
}
void merg(int a, int b) {
a=par(a);
b=par(b);
if(a!=b) {
if(h[a]<h[b]) swap(a, b);
rod[b]=a;
h[a]+=h[b];
cnt[hesd[a]-heskd[a]].erase(a);
if(hesd[b]!=heskd[b]) --kolko;
if(hesd[a]==heskd[a]) ++kolko;
hesd[a]=((hesd[a]+hesd[b])%mod+mod)%mod;
heskd[a]=((heskd[a]+heskd[b])%mod+mod)%mod;
cnt[hesd[a]-heskd[a]].insert(a);
if(hesd[a]==heskd[a]) --kolko;
s.erase(b);
}
}
ll step(ll x, int y) {
if(y==0) return 1LL;
if(y==1) return x;
ll pola=step(x, y/2);
if(y&1) return ((pola*pola)%mod*x)%mod;
return (pola*pola)%mod;
}
int main() {
ios;
cin >> n >> q;
for(int i=1; i<=n; ++i) {
cin >> p[i];
rod[i]=i;
h[i]=1;
hes[i]=hesd[i]=step((p[i]+1LL), k);
kon[i]=p[i];
s.insert(i);
}
sort(kon+1, kon+1+n);
for(int i=1; i<=n; ++i) {
hesk[i]=heskd[i]=step((kon[i]+1LL), k);
cnt[hesd[i]-heskd[i]].insert(i);
if(hesd[i]!=heskd[i]) ++kolko;
}
while(q--) {
int t; cin >> t;
if(t<3) {
int x, y; cin >> x >> y;
if(t==1) {
int x1=par(x);
int y1=par(y);
if(x1!=y1) {
cnt[hesd[x1]-heskd[x1]].erase(x1);
if(hesd[x1]==heskd[x1]) ++kolko;
hesd[x1]-=hes[x];
hesd[x1]+=hes[y];
hesd[x1]=(hesd[x1]%mod+mod)%mod;
cnt[hesd[x1]-heskd[x1]].insert(x1);
if(hesd[x1]==heskd[x1]) --kolko;
cnt[hesd[y1]-heskd[y1]].erase(y1);
if(hesd[y1]==heskd[y1]) ++kolko;
hesd[y1]-=hes[y];
hesd[y1]+=hes[x];
hesd[y1]=(hesd[y1]%mod+mod)%mod;
cnt[hesd[y1]-heskd[y1]].insert(y1);
if(hesd[y1]==heskd[y1]) --kolko;
swap(hes[x], hes[y]);
}
}
else {
merg(x, y);
}
}
else if(t==3) {
if(kolko==0) cout << "DA\n";
else cout << "NE\n";
}
else {
ll br=0LL;
for(auto x:s) {
if(hesd[x]==heskd[x]) continue;
for(auto y:cnt[-hesd[x]+heskd[x]]) {
br+=h[x]*h[y];
}
}
cout << br/2 << "\n";
}
}
return 0;
}
