#include <bits/stdc++.h>
using namespace std;
#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
using ll = long long;
const int N = 1e6 + 5;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
ll Rand(ll l, ll r){return uniform_int_distribution<ll>(l, r)(rd);}
int n, q, a[2][N], par[N], sz[N], bad;
ll hsh[N], sum_hsh[2][N], answer;
map<ll, ll> hsh_counter;
ll cnt_hsh(ll pref){
return (pref != 0 && hsh_counter.count(pref) ? hsh_counter[pref] : 0ll);
}
int asc(int x){
return x == par[x] ? x : par[x] = asc(par[x]);
}
void upd_cnt(int x, int op){
if(sum_hsh[0][x] != sum_hsh[1][x]){
ll cur_sz = sz[asc(x)];
ll target = sum_hsh[1][x] - sum_hsh[0][x];
answer = answer + op * cur_sz * cnt_hsh(target);
hsh_counter[-target] += op * cur_sz;
}
}
void check_bad(int x, int op){
bad = bad + op * (sum_hsh[0][x] != sum_hsh[1][x]);
}
void preprocess(){
FOR(i, 1, n){
par[i] = i, sz[i] = 1;
sum_hsh[0][i] += hsh[a[0][i]];
sum_hsh[1][i] += hsh[a[1][i]];
check_bad(i, +1), upd_cnt(i, +1);
}
}
bool join(int u, int v){
u = asc(u), v = asc(v);
if(u != v){
if(sz[u] < sz[v]) swap(u, v);
upd_cnt(u, -1), upd_cnt(v, -1);
check_bad(u, -1), check_bad(v, -1);
sum_hsh[0][u] += sum_hsh[0][v];
sum_hsh[1][u] += sum_hsh[1][v];
par[v] = u, sz[u] += sz[v];
check_bad(u, +1), upd_cnt(u, +1);
return true;
}
return false;
}
void update_pos(int x, int y){
int par_x = asc(x), par_y = asc(y);
if(par_x == par_y){
swap(a[0][x], a[0][y]);
}
else{
upd_cnt(par_x, -1), upd_cnt(par_y, -1);
check_bad(par_x, -1), check_bad(par_y, -1);
sum_hsh[0][par_x] -= hsh[a[0][x]];
sum_hsh[0][par_y] -= hsh[a[0][y]];
swap(a[0][x], a[0][y]);
sum_hsh[0][par_x] += hsh[a[0][x]];
sum_hsh[0][par_y] += hsh[a[0][y]];
upd_cnt(par_x, +1), upd_cnt(par_y, +1);
check_bad(par_x, +1), check_bad(par_y, +1);
}
}
void solve()
{
cin >> n >> q;
FOR(i, 1, n){
cin >> a[0][i];
a[1][i] = a[0][i];
}
sort(a[1] + 1, a[1] + 1 + n);
vector<int> comp;
FOR(i, 1, n) comp.emplace_back(a[0][i]);
sort(all(comp)), compact(comp);
FOR(i, 1, n){
a[0][i] = lower_bound(all(comp), a[0][i]) - comp.begin() + 1;
a[1][i] = lower_bound(all(comp), a[1][i]) - comp.begin() + 1;
}
FOR(i, 1, sz(comp)) hsh[i] = Rand(1, 1e13);
preprocess();
while(q--){
int op; cin >> op;
if(op == 1){
int a,b; cin >> a >> b;
update_pos(a, b);
}
else if(op == 2){
int a,b; cin >> a >> b;
join(a, b);
}
else if(op == 3){
cout << (!bad ? "DA" : "NE") << "\n";
}
else cout << answer << "\n";
}
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#define name "InvMOD"
if(fopen(name".INP", "r")){
freopen(name".INP","r",stdin);
freopen(name".OUT","w",stdout);
}
int t = 1; //cin >> t;
while(t--) solve();
return 0;
}
