给定三个长为 $n$ 的数组 $a,b,c$, 满足 $1\le a_i,b_i,c_i\le n$ 且为整数。

你需要进行 $m$ 次操作，每次操作为：

1 k x：代表将 $a$ 序列的第 $k$ 个位置改为 $x$，即 $a_k := x$。

2 r：代表查询有多少个三元组 $(i,j,k)$, 满足 $1\le i < j < k\le r$, 且 $b_{a_i}=a_j=c_{a_k}$。

输入格式

第一行两个数 $n,m$。

第二行 $n$ 个数，按顺序表示序列 $a$ 中的元素。

第三行 $n$ 个数，按顺序表示序列 $b$ 中的元素。

第四行 $n$ 个数，按顺序表示序列 $c$ 中的元素。

之后 $m$ 行，每行形如 1 k x 或 2 r，意义如上述。

输出格式

对每个 $2$ 操作，输出一行一个数表示答案。

样例数据

样例输入

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

样例输出

3
0
2

子任务

Idea：Forever_Pursuit&nzhtl1477&w33z8kqrqk8zzzx33，

Solution：nzhtl1477&w33z8kqrqk8zzzx33，

Code：w33z8kqrqk8zzzx33，

Data：w33z8kqrqk8zzzx33&nzhtl1477

对于 $100\%$ 的数据，满足 $1\le n\le 2\times 10^5$，$1\le m\le 5 \times 10^4$，$1\le a_i,b_i,c_i,x,k,r\le n$。

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

• $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$