Problem: AquaMoon has three integer arrays a, b, c of length n, where 1 ≤ a_i, b_i, c_i ≤ n for all i.

In order to accelerate her potato farming, she organizes her farm in a manner based on these three arrays. She is now going to complete m operations to count how many potatoes she can get. Each operation will have one of the two types:

  1. AquaMoon reorganizes their farm and makes the k-th element of the array a equal to x. In other words, perform the assignment a_k := x. 
  2. Given a positive integer r, AquaMoon receives a potato for each triplet (i,j,k), such that 1≤ i<j<k≤ r, and b_{a_i}=a_j=c_{a_k}. Count the number of such triplets. 



As AquaMoon is busy finding the library, help her complete all of their operations.

Input

The first line contains two integers n, m (1≤ n≤ 2⋅10^5, 1≤ m≤ 5⋅10^4).

The second line contains n integers a_1, a_2, ...,a_n (1≤ a_i≤ n).

The third line contains n integers b_1, b_2, ...,b_n (1≤ b_i≤ n).

The fourth line contains n integers c_1, c_2, ...,c_n (1≤ c_i≤ n).

The next m lines describe operations, the i-th line describes the i-th operation in one of these two formats:

  * "1\ k\ x" (1≤ k,x≤ n), representing an operation of the first type. 
  * "2\ r" (1≤ r≤ n), representing an operation of the second type. 



It is guaranteed that there is at least one operation of the second type.

Output

For each operation of the second type print the answer.

Example

Input


5 4
1 2 3 4 5
2 3 4 5 1
5 1 2 3 4
2 5
1 2 3
2 4
2 5


Output


3
0
2

Note

For the first operation, the triplets are:

  * i=1, j=2, k=3 
  * i=2, j=3, k=4 
  * i=3, j=4, k=5 



There is no satisfying triplet for the third operation.

For the fourth operation, the triplets are:

  * i=2, j=4, k=5 
  * i=3, j=4, k=5 

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

#define MAXN 200006
#define SQRTN 210

namespace io {
const int __SIZE = (1 << 21) + 1;
char ibuf[__SIZE], *iS, *iT, obuf[__SIZE], *oS = obuf, *oT = oS + __SIZE - 1,
                                           __c, qu[55];
int __f, qr, _eof;
#define Gc()                                                                   \
  (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, __SIZE, stdin),               \
               (iS == iT ? EOF : *iS++))                                       \
            : *iS++)
inline void flush() { fwrite(obuf, 1, oS - obuf, stdout), oS = obuf; }
inline void gc(char &x) { x = Gc(); }
inline void pc(char x) {
  *oS++ = x;
  if (oS == oT)
    flush();
}
inline void pstr(const char *s) {
  int __len = strlen(s);
  for (__f = 0; __f < __len; ++__f)
    pc(s[__f]);
}
inline void gstr(char *s) {
  for (__c = Gc(); __c < 32 || __c > 126 || __c == ' ';)
    __c = Gc();
  for (; __c > 31 && __c < 127 && __c != ' '; ++s, __c = Gc())
    *s = __c;
  *s = 0;
}
template <class I> inline bool gi(I &x) {
  _eof = 0;
  for (__f = 1, __c = Gc(); (__c < '0' || __c > '9') && !_eof; __c = Gc()) {
    if (__c == '-')
      __f = -1;
    _eof |= __c == EOF;
  }
  for (x = 0; __c <= '9' && __c >= '0' && !_eof; __c = Gc())
    x = x * 10 + (__c & 15), _eof |= __c == EOF;
  x *= __f;
  return !_eof;
}
template <class I> inline void print(I x) {
  if (!x)
    pc('0');
  if (x < 0)
    pc('-'), x = -x;
  while (x)
    qu[++qr] = x % 10 + '0', x /= 10;
  while (qr)
    pc(qu[qr--]);
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_flusher_;
} // namespace io
using io::gc;
using io::gi;
using io::gstr;
using io::pc;
using io::print;
using io::pstr;

#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair

using ll = long long;
using pii = pair<int, int>;

int n;
int a[MAXN], X[MAXN], Y[MAXN];

int Xa[MAXN], Ya[MAXN];

int dyn[SQRTN + 5];
bool dynp[MAXN];

int ps1[MAXN];
ll ps2[MAXN];

ll ps_7j[MAXN];

int fake_a[MAXN], fake_Xa[MAXN], fake_Ya[MAXN];

struct offl {
  int val, id, nxt;
} detecpool[(SQRTN * SQRTN * 11) / 2 + 5];

int detec[MAXN];
int detec8f[MAXN];
int detecX[MAXN], detecY[MAXN];

int dryans[(SQRTN * SQRTN * 3) / 2 + 5];
int dryansX[(SQRTN * SQRTN) / 2 + 5];
int dryansY[(SQRTN * SQRTN * 4) / 2 + 5];
ll dryans_7[(SQRTN * SQRTN) / 2 + 5];
ll dryans_8_former[(SQRTN * SQRTN * 2) / 2 + 5];
ll ijk_static[MAXN];

void dryrun(vector<pii> ops) {
  copy(a, a + n, fake_a);
  copy(Xa, Xa + n, fake_Xa);
  copy(Ya, Ya + n, fake_Ya);
  memset(detec, -1, sizeof detec);
  memset(detecX, -1, sizeof detecX);
  memset(detecY, -1, sizeof detecY);
  memset(detec8f, -1, sizeof detec8f);
  int pooln = 0;
  auto push_back = [&](int *ve, int pos, int va, int id) {
    detecpool[pooln] = {va, id, ve[pos]};
    ve[pos] = pooln;
    pooln++;
  };
  int dryid = 0, dryidX = 0, dryidY = 0, dryid7 = 0, dryid8f = 0;
  for (auto [opn, r] : ops) {
    if (opn != -1) {
      assert(dynp[opn]);
      a[opn] = r;
      Xa[opn] = X[r];
      Ya[opn] = Y[r];
    } else {
      int mxdyn = 0;
      for (int i = 0; dyn[i] <= r; i++)
        mxdyn++;
      for (int _j = 0; _j < mxdyn; _j++) {
        int j = dyn[_j];
        int pfx_xai_km1 = 0;
        if (j != 0) {
          push_back(detecX, j - 1, a[j], dryidX++);
          push_back(detecY, r, a[j], dryidY++);
          push_back(detecY, j, a[j], dryidY++);

          int k = dyn[_j];
          push_back(detec, k - 1, Xa[k], dryid++);
          push_back(detec, k - 1, Ya[k], dryid++);
        }
        int i = j;
        if (i != r) {
          push_back(detec8f, i + 1, Xa[i], dryid8f++);
          push_back(detec8f, r + 1, Xa[i], dryid8f++);
          push_back(detec, r, Xa[i], dryid++);
          push_back(detecY, n, Xa[i], dryidY++);
          push_back(detecY, r, Xa[i], dryidY++);
        }
      }
    }
  }
  for (int i = 0; i <= n; i++) {
    if (i != n && !dynp[i]) {
      ps1[a[i]]++;
    }
    for (int pid = detec[i]; pid != -1; pid = detecpool[pid].nxt)
      dryans[detecpool[pid].id] = ps1[detecpool[pid].val];
  }
  memset(ps1, 0, n * (sizeof(int)));
  ll cpsm = 0;
  for (int i = 0; i <= n; i++) {
    if (i != n && !dynp[i]) {
      cpsm += ps_7j[Ya[i]];
      ps_7j[a[i]] += ps1[a[i]];
      ps1[Xa[i]]++;
    }
    ijk_static[i] = cpsm;
    for (int pid = detecX[i]; pid != -1; pid = detecpool[pid].nxt) {
      dryansX[detecpool[pid].id] = ps1[detecpool[pid].val];
      dryans_7[detecpool[pid].id] = ps_7j[Y[detecpool[pid].val]];
    }
  }
  memset(ps1, 0, n * (sizeof(int)));
  for (int i = 0; i <= n; i++) {
    if (i != n && !dynp[i]) {
      ps1[Ya[i]]++;
    }
    for (int pid = detecY[i]; pid != -1; pid = detecpool[pid].nxt)
      dryansY[detecpool[pid].id] = ps1[detecpool[pid].val];
  }
  memset(ps1, 0, n * (sizeof(int)));
  memset(ps_7j, 0, n * (sizeof(ll)));

  for (int i = n; i >= 0; i--) {
    if (i != n && !dynp[i]) {
      ps2[a[i]] += ps1[a[i]];
      ps1[Ya[i]]++;
    }
    for (int pid = detec8f[i]; pid != -1; pid = detecpool[pid].nxt)
      dryans_8_former[detecpool[pid].id] = ps2[detecpool[pid].val];
  }
  memset(ps1, 0, n * (sizeof(int)));
  memset(ps2, 0, n * (sizeof(ll)));
  copy(fake_a, fake_a + n, a);
  copy(fake_Xa, fake_Xa + n, Xa);
  copy(fake_Ya, fake_Ya + n, Ya);
}

int PfxGud3[MAXN], SfxGud4[MAXN];

void process(vector<pii> ops) {
  set<int> mdfd;
  for (auto [xx, b] : ops)
    if (xx != -1)
      mdfd.insert(xx);
  int dync = 0;
  memset(dyn, 1, sizeof dyn);
  for (int i : mdfd)
    dyn[dync++] = i;
  memset(dynp, 0, sizeof dynp);
  for (int i = 0; i < dync; i++)
    dynp[dyn[i]] = 1;
  dryrun(ops);
  int dryid = 0, dryidX = 0, dryidY = 0, dryid6l = 0, dryid7 = 0, dryid8f = 0;
  for (auto [opn, r] : ops) {
    if (opn != -1) {
      a[opn] = r;
      Xa[opn] = X[r];
      Ya[opn] = Y[r];
    } else {
      int mxdyn = 0;
      for (int i = 0; dyn[i] <= r; i++)
        mxdyn++;
      ll P1 = ijk_static[r], P2 = 0, P3 = 0, P4 = 0, P5 = 0, P6 = 0, P7 = 0,
         P8 = 0;
      for (int _i = 0; _i < mxdyn; _i++) {
        int i = dyn[_i];
        PfxGud3[i] = ps1[a[i]];
        P2 += ps2[Ya[i]];
        ps2[a[i]] += ps1[a[i]];
        ps1[Xa[i]]++;
      }
      for (int _i = 0; _i < mxdyn; _i++) {
        int i = dyn[_i];
        ps2[a[i]] = 0;
        ps1[Xa[i]] = 0;
      }
      for (int _i = mxdyn - 1; _i >= 0; _i--) {
        int i = dyn[_i];
        SfxGud4[i] = ps1[a[i]];
        ps1[Ya[i]]++;
      }
      for (int _i = 0; _i < mxdyn; _i++) {
        int i = dyn[_i];
        ps1[Ya[i]] = 0;
      }
      for (int _j = 0; _j < mxdyn; _j++) {
        int j = dyn[_j];
        int pfx_xai_km1 = 0;
        if (j != 0) {
          int pfx_ixaj_jm1 = dryansX[dryidX++];
          int pfx_iyaj_r = dryansY[dryidY++];
          int pfx_iyaj_j = dryansY[dryidY++];
          P3 += PfxGud3[j] * (pfx_iyaj_r - pfx_iyaj_j);
          P4 += pfx_ixaj_jm1 * SfxGud4[j];
          P5 += 1ll * pfx_ixaj_jm1 * (pfx_iyaj_r - pfx_iyaj_j);

          int k = dyn[_j];
          pfx_xai_km1 = dryans[dryid++];
          int pfx_yak_km1 = dryans[dryid++];
          int pfxDyn_ixyak = ps1[Ya[k]];
          ll pfxDyn_BAD_ixyak = ps2[Ya[k]];
          ps1[Xa[k]]++;
          ps2[Xa[k]] += pfx_xai_km1;
          P6 += 1ll * pfx_yak_km1 * pfxDyn_ixyak - pfxDyn_BAD_ixyak;

          P7 += dryans_7[dryid7++];
        } else {
          ps1[Xa[j]]++;
        }
        int i = j;
        if (i != r) {
          ll sfx_xai_ip1 = dryans_8_former[dryid8f++];
          ll sfx_xai_rp1 = dryans_8_former[dryid8f++];
          int pfx_xai_r = dryans[dryid++];
          int pfx_xai_i = pfx_xai_km1;
          int pfx_iyxai_n = dryansY[dryidY++];
          int pfx_iyxai_r = dryansY[dryidY++];
          P8 += (sfx_xai_ip1 - sfx_xai_rp1) -
                1ll * (pfx_xai_r - pfx_xai_i) * (pfx_iyxai_n - pfx_iyxai_r);
        }
      }
      for (int _i = 0; _i < mxdyn; _i++) {
        int i = dyn[_i];
        ps2[Xa[i]] = 0;
        ps1[Xa[i]] = 0;
      }
      print(P1 + P2 + P3 + P4 + P5 + P6 + P7 + P8);
      pc('\n');
    }
  }
}

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  int m;
  gi(n), gi(m);
  for (int i = 0; i < n; i++) {
    gi(a[i]);
    a[i]--;
  }
  for (int i = 0; i < n; i++) {
    gi(X[i]);
    X[i]--;
  }
  for (int i = 0; i < n; i++) {
    gi(Y[i]);
    Y[i]--;
  }
  for (int i = 0; i < n; i++) {
    Xa[i] = X[a[i]];
    Ya[i] = Y[a[i]];
  }
  vector<pii> opq;
  for (int qx = 0; qx < m; qx++) {
    int op, v;
    gi(op);
    gi(v);
    if (op == 1) {
      int r;
      gi(r);
      opq.push_back({v - 1, r - 1});
    } else {
      opq.push_back({-1, v - 1});
    }
    if (opq.size() == SQRTN) {
      process(opq);
      opq.clear();
    }
  }
  process(opq);
}