Permutation Chain Query

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. Each operation is one of the following two types:

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

Note that a single element interval \([i,i]\) is considered valid since the chain property is vacuously true, and it is counted if \(a_i=x\).

inputFormat

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

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\).

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

The next \(m\) lines each describe an operation. An operation is given in one of the following formats:

• For a modification: 1 x y (change \(a_x\) to \(y\)).
• For a query: 2 l r x (query the subinterval \([l, r]\) for the chain property with at least one occurrence of \(x\)).

outputFormat

For each query operation, output a single line containing one integer: the maximum length of a subinterval within \([l,r]\) that satisfies the chain condition \(a_{i+1} = b_{a_i}\) for every consecutive pair and also contains at least one element equal to \(x\). If no such subinterval exists, output \(0\).

sample

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

1
2
1