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

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

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

2 r: Query the number of triples $(i, j, k)$ such that $1 \le i < j < k \le r$ and $b_{a_i} = a_j = c_{a_k}$.

Input

The first line contains two integers $n$ and $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.

The following $m$ lines each contain an operation of the form 1 k x or 2 r, as described above.

Output

For each 2 operation, output one integer per line representing the answer.

Examples

Input 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

Output 1

3
0
2

Subtasks

Idea: Forever_Pursuit & nzhtl1477 & w33z8kqrqk8zzzx33,

Solution: nzhtl1477 & w33z8kqrqk8zzzx33,

Code: w33z8kqrqk8zzzx33,

Data: w33z8kqrqk8zzzx33 & nzhtl1477

For $100\%$ of the data, $1 \le n \le 2 \times 10^5$, $1 \le m \le 5 \times 10^4$, and $1 \le a_i, b_i, c_i, x, k, r \le n$.

Note

For the first operation, the triples satisfying 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 satisfying the condition.

For the fourth operation, the triples satisfying the condition are:

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