Problem Description

Given three arrays $a, b, c$ of length $n$, where $1 \le a_i, b_i, c_i \le n$ and all are integers.

You need to perform $m$ operations. Each operation is one of the following:

1 k x: Modify the $k$-th position of array $a$ to $x$, i.e., $a_k := x$.

2 r: Query how many triples $(i, j, k)$ satisfy $1 \le i < j < k \le r$ and $b_{a_i} = a_j = c_{a_k}$.

Input Format

The first line contains two integers $n, m$.

The second line contains $n$ integers, representing the elements of array $a$ in order.

The third line contains $n$ integers, representing the elements of array $b$ in order.

The fourth line contains $n$ integers, representing the elements of array $c$ in order.

Then follow $m$ lines, each in the form 1 k x or 2 r, with the meaning as described above.

Output Format

For each operation of type $2$, output one line containing one integer representing the answer.

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

Hint

Idea: Forever_Pursuit&nzhtl1477&w33z8kqrqk8zzzx33。

Solution: nzhtl1477&w33z8kqrqk8zzzx33。

Code: w33z8kqrqk8zzzx33。

Data: w33z8kqrqk8zzzx33&nzhtl1477。

For $100\%$ of the testdata, $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$.

For the first operation, the triples that satisfy the condition are:

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

For the third operation, there are no triples that satisfy the condition.

For the fourth operation, the triples that satisfy the condition are:

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

Translated by ChatGPT 5