AquaMoon 有三个整数数组 $$$a$$$、$$$b$$$、$$$c$$$,长度为 $$$n$$$,其中 $$$1 \leq a_i、b_i、c_i \leq n$$$ 代表所有 $$$i$$$。
为了加速她的马铃薯种植,她按照这三个数组的方式组织她的农场。她现在将完成 $$$m$$$ 操作来计算她可以获得多少个土豆。每个操作都有以下两种类型之一:
1. AquaMoon 重新组织他们的农场,并使数组 $$$a$$$ 的第 $$$k$$$ 元素等于 $$$x$$$。换句话说,执行赋值 $$$a_k := x$$$。
2. 给定一个正整数 $$$r$$$,AquaMoon 会为每个三元组 $$$(i,j,k)$$$ 接收一个土豆,使得 $$$1\le i<j<k\le r$$$,并且 $$$b_{a_i}=a_j=c_{a_k}$$$。计算这样的三元组的数量。
由于AquaMoon正忙于寻找图书馆,请帮助她完成所有操作。
输入
第一行包含两个整数 $$$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$$$),表示第二类操作。
保证至少有一个第二类型的操作。
输出
对于第二种类型的每个操作,打印答案。
示例
输入 #1
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
输出 #1
3 0 2
注意
对于第一个操作,三元组是:
- $$$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$$$