Description

Little O has a permutation $p$ of length $n$. His good friend $\texttt{euei}$ has a sequence $a$ of length $n$, with values in $[1, n]$.

One day, Little O suddenly wondered whether there exists a pair of indices $i, j$ such that $l \le i, j \le r$ and $p_{a_i} = a_j$. He solved this problem easily. However, $\texttt{euei}$ sometimes modifies the value at some position in this sequence, and also asks the above question for many different pairs $l, r$. Now Little O does not know how to handle it.

Can you, the smart one, help Little O solve this problem?

Input Format

The first line contains two positive integers $n, m$, where $m$ is the total number of modifications and queries.

The second line contains $n$ positive integers $p_1, p_2, \cdots, p_n$, representing the permutation $p$.

The third line contains $n$ positive integers $a_1, a_2, \cdots, a_n$, representing the initial sequence $a$.

The next $m$ lines each contain three positive integers, in one of the following two formats:

• 1 i v, meaning set $a_i$ to $v$.
• 2 l r, meaning query whether there exists a pair of indices $i, j$ such that $l \le i, j \le r$ and $p_{a_i} = a_j$.

Output Format

For each query, if such a pair exists, output Yes; otherwise output No.

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

Yes
No

Hint

Hint

The input size is large, so please use a fast input method.

Explanation of the samples

For the first query, the pair $2, 3$ satisfies the requirement.

For the second query, no pair satisfies the requirement.

Constraints

This problem has $5$ subtasks. You must pass all test points within a subtask to get the score for that subtask.

For all testdata, $1 \le n,m \le 5\times 10^5$, $1 \le a_i, i, v, l, r \le n$, $p_i \neq i$.

Blank entries in the table mean there are no special restrictions for that item.

Translated by ChatGPT 5