Problem Description

Given a sequence $a_1,\dots,a_n$ and a permutation $b_1,\dots,b_n$, there are $m$ operations in total:

• Modify operation: given $x,y$, change $a_x$ to $y$.
• Query operation: given $l,r,x$, find the longest sub-interval $[l',r']$ within $[l,r]$ (i.e., satisfying $l\le l'\le r'\le r$) such that for all $l'\le i<r'$, we have $a_{i+1}=b_{a_i}$, and there exists some $l'\le i\le r'$ with $a_i=x$. You need to output the maximum possible value of $r'-l'+1$ that satisfies the conditions; if no such interval exists, output $0$.

Input Format

The first line contains two integers $n,m$.

The second line contains $n$ integers, representing $a_1,\dots,a_n$ in order.

The third line contains $n$ integers, representing $b_1,\dots,b_n$ in order.

The next $m$ lines each contain either $1,x,y$ or $2,l,r,x$, indicating one modify operation or one query operation.

All input values are integers.

Output Format

For each query operation, output one line containing the corresponding answer.

8 10
1 4 7 3 8 2 4 7
5 4 8 7 1 6 3 2
2 6 6 2
2 8 8 7
1 4 3
2 6 8 3
2 4 4 3
2 4 4 3
2 6 8 4
2 5 6 2
2 1 8 1
2 1 1 6

1
1
0
1
1
3
2
1
0

Hint

Constraints:

$1\le n,m\le 10^6$.

$1\le a_i\le n$.

$1\le b_i\le n$, and all $b_i$ are distinct.

For modify operations, $1\le x,y\le n$.

For query operations, $1\le l\le r\le n$, $1\le x\le n$.

Translated by ChatGPT 5