Sequence and Permutation Operations

You are given a sequence \(a_1,a_2,\dots,a_n\) and a permutation \(b_1,b_2,\dots,b_n\). There are \(m\) operations of two types:

• Modification operation: Given integers \(x\) and \(y\), update \(a_x\) to \(y\).
• Query operation: Given integers \(l,r,x\), find the longest contiguous subinterval \([l',r']\) within \([l,r]\) (i.e. \(l\le l'\le r'\le r\)) such that for every index \(i\) with \(l'\le i<r'\) the following chain condition holds: \[ a_{i+1} = b_{a_i}, \] and there exists at least one index \(i\) in \([l',r']\) with \(a_i=x\). Output the length \(r'-l'+1\) of the longest such interval. If no such interval exists, output \(0\).

Note: All formulas are written in \(\LaTeX\) format.

inputFormat

The first line contains two integers \(n\) and \(m\) (the size of the sequence and the number of operations).

The second line contains \(n\) integers \(a_1,a_2,\dots,a_n\) representing the initial sequence.

The third line contains \(n\) integers \(b_1,b_2,\dots,b_n\) which form a permutation of \(\{1,2,\dots,n\}\).

Then \(m\) lines follow, each describing an operation. An operation is either:

• Type 1 (modification): 1 x y (update \(a_x\) to \(y\)); or
• Type 2 (query): 2 l r x (query on the interval \([l, r]\) with target value \(x\)).

outputFormat

For each query operation, output one integer representing the maximum length of a contiguous subinterval which satisfies the chain condition and contains at least one occurrence of \(x\). If no such interval exists, output \(0\).

sample

5 5
1 2 3 4 5
2 3 4 5 1
2 1 5 2
1 3 1
2 1 5 1
2 2 4 4
2 3 5 5

5
2
1
2