A14446 | AquaMoon and Potatoes

# Subscribe to Technoblade

Technoblade has three integer arrays $a$, $b$, $c$ of length $n$. We have $1 \leq a_i, b_i, c_i \leq n$ for all $i$.

In order to accelerate his potato farming, he organizes his farm in a manner based on these three arrays. He is now going to complete $m$ operations to count how many potatoes he can get. Each operation will be in one of the two following forms:

1. Technoblade reorganizes his 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$, Technoblade receives a potato for each triplet $(i,j,k)$, such that $1\le i<j<k\le r$, and $b_{a_i}=a_j=c_{a_k}$. Count the number of potatoes that he receives; that is, the number of such triplets.

Help Technoblade complete these operations.

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.