Big Data Permutation

You are given a sequence $a_1, \ldots, a_n$ and a permutation $b_1, \ldots, b_n$. Process $m$ operations of the following two kinds.

• Modification: given $x$ and $y$, change $a_x$ to $y$.
• Query: given $\ell$, $r$, and $x$, find the longest sub-interval $[\ell', r']$ of $[\ell, r]$ (that is, $\ell \le \ell' \le r' \le r$) such that $a_{j+1} = b_{a_j}$ for every $\ell' \le j < r'$, and there is some $i$ with $\ell' \le i \le r'$ and $a_i = x$. Output only the maximum length $r' - \ell' + 1$. If there is no such interval, output $0$.

The first line contains $n$ and $m$ ($1 \le n, m \le 10^6$). The second line contains $a_1, \ldots, a_n$ ($1 \le a_i \le n$). The third line contains $b_1, \ldots, b_n$ ($1 \le b_i \le n$; all $b_i$ are distinct). Each of the next $m$ lines is either 1 x y for a modification or 2 l r x for a query ($1 \le x, y \le n$; $1 \le \ell \le r \le n$). There is at least one query.

For each query, print the answer on its own line.