CF1545F.AquaMoon and Potatoes

AquaMoon has three integer arrays $a$, $b$, $c$ of length $n$, where $1 \leq a_i, b_i, c_i \leq 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\le i \lt j \lt k\le 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.

AquaMoon 有三个长度为 $n$ 的整数数组 $a$、$b$、$c$，其中对所有 $i$ 均满足 $1 \leq a_i, b_i, c_i \leq n$。

为了加速她的土豆种植，她依据这三个数组来规划农场布局。现在她将执行 $m$ 个操作，以统计她能收获多少土豆。每个操作属于以下两种类型之一：

1. AquaMoon 重新规划农场，将数组 $a$ 的第 $k$ 个元素修改为 $x$。即执行赋值操作 $a_k := x$。
2. 给定一个正整数 $r$，AquaMoon 对每个满足 $1\le i \lt j \lt k\le r$ 且 $b_{a_i}=a_j=c_{a_k}$ 的三元组 $(i,j,k)$ 收获一个土豆。统计满足条件的三元组个数。

由于 AquaMoon 正忙于寻找图书馆，请你帮她完成所有这些操作。

The first line contains two integers $n$, $m$ ($1\le n\le 2\cdot10^5$, $1\le m\le 5\cdot10^4$).

The second line contains $n$ integers $a_1, a_2, \dots,a_n$ ($1\le a_i\le n$).

The third line contains $n$ integers $b_1, b_2, \dots,b_n$ ($1\le b_i\le n$).

The fourth line contains $n$ integers $c_1, c_2, \dots,c_n$ ($1\le c_i\le 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\le k,x\le n$), representing an operation of the first type.
• "$2\ r$" ($1\le r\le n$), representing an operation of the second type.

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

第一行包含两个整数 $n$、$m$（$1\le n\le 2\cdot10^5$，$1\le m\le 5\cdot10^4$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots,a_n$（$1\le a_i\le n$）。

第三行包含 $n$ 个整数 $b_1, b_2, \dots,b_n$（$1\le b_i\le n$）。

第四行包含 $n$ 个整数 $c_1, c_2, \dots,c_n$（$1\le c_i\le n$）。

接下来的 $m$ 行描述操作，其中第 $i$ 行描述第 $i$ 个操作，格式为以下两种之一：

• “$1\ k\ x$”（$1\le k,x\le n$），表示第一类操作。
• “$2\ r$”（$1\le r\le n$），表示第二类操作。

保证至少存在一个第二类操作。

For each operation of the second type print the answer.

对于每种第二类操作，请输出答案。

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$

对于第一次操作，满足条件的三元组为：

• $i=1$, $j=2$, $k=3$
• $i=2$, $j=3$, $k=4$
• $i=3$, $j=4$, $k=5$

第三次操作不存在满足条件的三元组。

对于第四次操作，满足条件的三元组为：

• $i=2$, $j=4$, $k=5$
• $i=3$, $j=4$, $k=5$