#include <cstdio>
#include <algorithm>
using namespace std;
int n, pos[3][100001], seg[400001], seg2[400001];
void update(int v, int tl, int tr, int pos, int x) {
if (tl == tr) {
seg[v] += x;
seg2[v] += x;
} else {
int tm = (tl+tr) >> 1;
if (pos <= tm) update(v<<1, tl, tm, pos, x);
else update(v<<1|1, tm+1, tr, pos, x);
seg[v] = min(seg[v<<1], seg2[v<<1]+seg[v<<1|1]);
seg2[v] = seg2[v<<1]+seg2[v<<1|1];
}
}
int query(int v, int tl, int tr, int s) {
if (tl == tr) return tl;
int tm = (tl+tr) >> 1;
if (seg[v<<1] <= s) return query(v<<1, tl, tm, s);
return query(v<<1|1, tm+1, tr, s-seg2[v<<1]);
}
void change(int v, int x) {
update(1, 1, n, min(min(pos[0][v], pos[1][v]), pos[2][v]), x);
update(1, 1, n, max(max(pos[0][v], pos[1][v]), pos[2][v]), -x);
}
int main() {
int q, t, x, y, z, cur = -1;
scanf("%d%d", &n, &q);
for (int i=0; i<3; i++) {
for (int j=1; j<=n; j++) {
scanf("%d", &x);
pos[i][x] = j;
}
}
for (int i=1; i<=n; i++) change(i, 1);
while (q--) {
scanf("%d%d", &t, &x);
if (t == 1) printf(pos[0][x] <= (cur == -1 ? cur = query(1, 1, n, 0) : cur) ? "DA\n" : "NE\n");
else {
scanf("%d%d", &y, &z);
change(y, -1);
change(z, -1);
swap(pos[x-1][y], pos[x-1][z]);
change(y, 1);
change(z, 1);
cur = -1;
}
}
}
