Dynamic Sequence Query with Permutation Mapping

Given a permutation (p) of length (n) and a sequence (a) of length (n) with values in ([1, n]), you are to process (m) operations. Initially, you are given the permutation (p = [p_1, p_2, \ldots, p_n]) and the sequence (a = [a_1, a_2, \ldots, a_n]). There are two types of operations:

• Update Operation: In the form 1 i x, update \(a_i\) to \(x\) (i.e. assign \(a_i = x\)).
• Query Operation: In the form 2 l r, determine whether there exist indices \(i\) and \(j\) (they may be the same) with \(l \le i, j \le r\) such that \(p_{a_i} = a_j\). In other words, let \(S = \{a_l, a_{l+1}, \ldots, a_r\}\); the answer is Yes if there exists an element \(x \in S\) with \(p(x) \in S\) (noting that if \(p(x)=x\), a single occurrence suffices), and No otherwise.

Your task is to answer all the queries as the sequence (a) is updated.

inputFormat

The first line contains two integers \(n\) and \(m\) denoting the length of the permutation and the number of operations.

The second line contains \(n\) integers \(p_1, p_2, \ldots, p_n\) representing the permutation \(p\).

The third line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) representing the sequence \(a\) where \(1 \le a_i \le n\).

The following \(m\) lines each describe an operation in one of the following forms:

• 1 i x — update operation: set \(a_i = x\) (with \(1 \le i \le n\) and \(1 \le x \le n\)).
• 2 l r — query operation: determine if there exist indices \(i, j\) with \(l \le i, j \le r\) such that \(p_{a_i} = a_j\). Output Yes if the condition is met, otherwise No.

outputFormat

For each query operation (2 l r), print a single line containing Yes if there exists at least one \(x\) in \(\{a_l, a_{l+1}, \ldots, a_r\}\) with \(p(x) \in \{a_l, a_{l+1}, \ldots, a_r\}\), and No otherwise.

sample

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

Yes
Yes
Yes
Yes