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 form:

• Modification operation: given $x$ and $y$, change $a_x$ into $y$.
• Query operation: given $\ell$, $r$, and $x$, find the longest sub-interval $[\ell', r']$ within the interval $[\ell, r]$ (formally, $\ell \le \ell' \le r' \le r$) such that, for $\ell' \le j < r'$, we have $a_{j + 1} = b_{a_j}$, and additionally, there exists an $i$ such that $\ell' \le i \le r'$ and $a_i = x$. You only need to output the maximum length of such sub-interval (formally, $r' - \ell' + 1$); if there is none, output $0$.

The first line of input contains two integers $n$ and $m$ ($1 \le n, m \le 10^6$).

The second line contains $n$ integers $a_1, \ldots, a_n$ ($1 \le a_i \le n$).

The third line contains $n$ integers $b_1, \ldots, b_n$ ($1 \le b_i \le n$; all $b_i$ are distinct).

Each of the next $m$ lines consists of integers and has either the form "1~$x$~$y$" for a modification operation or the form "2~$\ell$~$r$~$x$" for a query operation ($1 \le x, y \le n$; $1 \le \ell \le r \le n$).

You may assume that there is at least one query operation.

For each query operation, output one line with the corresponding maximum length.