#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
#define ull unsigned ll
const int mxN=1e6;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, q, a[mxN], b[mxN], p[mxN], s[mxN], bad;
ull val[mxN], h1[mxN], h2[mxN];
unordered_map<ull, ll> mp;
ll ans;
int find(int i) {
return i^p[i]?p[i]=find(p[i]):i;
}
void add(int u) {
assert(p[u]==u);
if (h1[u]^h2[u]) {
++bad;
mp[h1[u]-h2[u]]+=s[u];
auto it=mp.find(h2[u]-h1[u]);
if (it!=mp.end())
ans+=s[u]*it->second;
}
}
void rem(int u) {
assert(p[u]==u);
if (h1[u]^h2[u]) {
--bad;
auto it=mp.find(h1[u]-h2[u]);
assert(it!=mp.end());
if ((it->second-=s[u])==0)
mp.erase(it);
it=mp.find(h2[u]-h1[u]);
if (it!=mp.end())
ans-=s[u]*it->second;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
for (int i=0; i<n; ++i) {
cin >> a[i], --a[i];
b[i]=a[i];
}
sort(b, b+n);
for (int i=0; i<mxN; ++i)
val[i]=rng();
for (int i=0; i<n; ++i) {
p[i]=i, s[i]=1;
h1[i]=val[a[i]];
h2[i]=val[b[i]];
add(i);
}
while(q--) {
int t;
cin >> t;
if (t==1) {
int x, y;
cin >> x >> y, --x, --y;
int u=find(x), v=find(y);
if (u==v) {
swap(a[x], a[y]);
continue;
}
rem(u), rem(v);
h1[u]-=val[a[x]], h1[v]-=val[a[y]];
swap(a[x], a[y]);
h1[u]+=val[a[x]], h1[v]+=val[a[y]];
add(u), add(v);
} else if (t==2) {
int x, y;
cin >> x >> y, --x, --y;
int u=find(x), v=find(y);
if (u==v)
continue;
if (s[u]<s[v])
swap(u, v);
rem(u), rem(v);
p[v]=u, s[u]+=s[v];
h1[u]+=h1[v], h2[u]+=h2[v];
add(u);
} else if (t==3) {
cout << (!bad?"DA":"NE") << "\n";
} else {
cout << ans << "\n";
}
}
return 0;
}
