#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
const ll LOG = 31;
const ll MOD = 1e15 + 37;
const ll inf = 1e17;
const ll b = 131, N = 1e6;
#define db(x) cerr << #x << " = " << x << " | "
#define dbg(x) cerr << #x << " = " << x << "\n"
#define all(a) a.begin(), a.end()
#define Algerian ios::sync_with_stdio(0);
#define OI cin.tie(NULL);
ll po[N + 1];
ll add(ll x, ll y) {
return (((x + y) % MOD) + MOD) % MOD;
}
struct DSU {
vector<ll> s, p, hsh, a;
ll cnt = 0;
map<ll, ll> frq;
void add_hsh(ll h, ll sz) {
if (h == 0) return;
if (frq.count(MOD - h)) cnt += frq[MOD - h] * sz;
frq[h] += sz;
}
void rem_hsh(ll h, ll sz) {
if (h == 0) return;
frq[h] -= sz;
if (frq.count(MOD - h)) cnt -= frq[MOD - h] * sz;
if (!frq[h]) frq.erase(h);
}
DSU(vector<ll> A, vector<ll> b, ll n) {
a = A;
s.assign(n, 1);
p.resize(n, 1);
iota(p.begin(), p.begin() + n, 0);
// iota(p.begin() + n, p.end(), n);
hsh.assign(n, 0);
for (ll i = 0; i < n; i++) {
hsh[i] = add(po[a[i]], -po[b[i]]);
if (hsh[i] != 0) add_hsh(hsh[i], 1);
}
}
ll par(ll x) { return x == p[x] ? x : p[x] = par(p[x]); }
void merge(ll u, ll v) {
u = par(u), v = par(v);
if (u == v) return;
if (s[u] < s[v]) swap(u, v);
rem_hsh(hsh[u], s[u]);
rem_hsh(hsh[v], s[v]);
s[u] += s[v];
p[v] = u;
hsh[u] = (hsh[u] + hsh[v]) % MOD;
add_hsh(hsh[u], s[u]);
}
void swp(ll u, ll v) {
ll x = par(u), y = par(v);
rem_hsh(hsh[x], s[x]);
hsh[x] = add(hsh[x], -po[a[u]]);
hsh[x] = add(hsh[x], po[a[v]]);
add_hsh(hsh[x], s[x]);
rem_hsh(hsh[y], s[y]);
hsh[y] = add(hsh[y], -po[a[v]]);
hsh[y] = add(hsh[y], po[a[u]]);
add_hsh(hsh[y], s[y]);
swap(a[u], a[v]);
}
bool pos() {
return !frq.size();
}
ll count() {
return cnt;
}
};
int main() {
Algerian OI
ll n, q;
cin >> n >> q;
po[0] = 1;
for (ll i = 1; i <= N; i++) {
po[i] = po[i - 1] * b % MOD;
}
vector<ll> p(n);
for (ll& x : p) cin >> x;
auto qu = p;
sort(all(qu));
DSU dsu(p, qu, n);
while (q--) {
ll t, u, v;
cin >> t;
if (t == 1) {
cin >> u >> v;
--u; --v;
dsu.swp(u, v);
} else if (t == 2) {
cin >> u >> v;
--u; --v;
dsu.merge(u, v);
} else if (t == 3) {
cout << (dsu.pos() ? "DA\n" : "NE\n");
} else {
cout << dsu.count() << "\n";
}
}
return 0;
}
/*
4 4
1 2 4 3
4
2 2 3
2 1 2
4
*/
