33261번 - 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.

제한

힌트