#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define chmin(a, b) a = min(a,b)
#define chmax(a, b) a = max(a,b)
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define all(x) x.begin(),x.end()
#define v vector
const int MAX_N = 1e6;
ll hsh[MAX_N], h[MAX_N];
int sz[MAX_N], par[MAX_N];
int p[MAX_N], q[MAX_N];
map<ll,int> paired;
ll pairs = 0;
int get(int x) {return (par[x]==x ? x : par[x]=get(par[x]));}
void upd_pair(int a, int m) {
if (hsh[a]) {
pairs += (ll)m*sz[a]*paired[-hsh[a]];
paired[hsh[a]] += m*sz[a];
}
}
void unite(int x, int y) {
int a = get(x), b = get(y);
if (a==b) {return;}
upd_pair(a,-1); upd_pair(b,-1);
if (sz[a]<sz[b]) {swap(a,b);}
par[b] = a; sz[a] += sz[b]; hsh[a] += hsh[b];
// merge sets
upd_pair(a,1);
}
void swp(int x, int y) {
int a = get(x), b = get(y);
if (a==b) {return;}
upd_pair(a,-1); upd_pair(b,-1);
hsh[a] += h[p[y]]-h[p[x]];
hsh[b] += h[p[x]]-h[p[y]];
swap(p[x],p[y]);
upd_pair(a,1); upd_pair(b,1);
}
void pre() {
mt19937 gen(std::chrono::steady_clock::now().time_since_epoch().count());
F0R(i,MAX_N) {h[i] = uniform_int_distribution<ll>(0,INT32_MAX)(gen);}
F0R(i,MAX_N) {
par[i] = i;
sz[i] = 1;
}
// c1+c2=p1+p2; c1-p1 = -(c2-p2)
// let hash be c-p
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
pre();
int n, nq; cin >> n >> nq;
F0R(i,n) {
cin >> p[i];
q[i] = p[i];
}
sort(q,q+n);
F0R(i,n) {
hsh[i] = h[p[i]]-h[q[i]];
}
F0R(i,n) {upd_pair(i,1);}
//cout<<pairs<<'\n';
while (nq--) {
int t; cin >> t;
if (t==1) {
int a, b; cin >> a >> b;
swp(--a,--b);
} else if (t==2) {
int a, b; cin >> a >> b;
unite(--a,--b);
} else if (t==3) {
cout << (pairs ? "NE" : "DA") << '\n';
} else {
cout << pairs << '\n';
}
}
/*
dsu for links
set of elements in comp = set of positions in comp, then it's good
maintain which nums are missing from each component
check for first missing check for what component it's in do hashes equal
if so then add 1 to type 4 query thing
upd that whenever updating a component
1) if comp of a and b are different, update their components by
deleting corresponding pairs, change hashes, upd corresponding pairs
xor hashing is easiest
2) delete corresponding pairs merge upd pairs
3) count if all components are good
4) return # pairs (return size of paired set / 2)
upd pair:
maintain set of positions for each, delete from set if is contained
query set and check the position of that element and check hash
and add/remove from paired set
swap:
if they were in their sets, delete them
and if the new thing is in the set, add them back
*/
}
