Background

xht37 has recently been addicted to Detective Conan.

In one episode, Ran suspects Conan’s true identity again. To stop Ran from suspecting him, Conan makes up a family background to answer Ran’s questions.

Problem Description

This family initially has only one person. Later, people keep having children, and up to now the family has $n$ people. Person $n$ is Conan. It is easy to see that this family forms a tree structure with $n$ nodes.

To make his made-up family background more realistic, Conan assigns each person an IQ value. However, a person’s smartness is not only related to their IQ value, but may also depend on their ancestors’ smartness and the era when they were born.

Specifically, in this family, A is smarter than B if and only if A and B satisfy one of the following three conditions:

1. A’s IQ value is higher than B’s IQ value.
2. A’s IQ value equals B’s IQ value, and A and B have different fathers; A’s father is smarter than B’s father.
3. A’s IQ value equals B’s IQ value, and A and B have the same father or one of them has no father; A is born later than B.

An obvious conclusion is that no two people in this family are equally smart.

Conan needs to answer Ran’s $q$ queries. For convenience, assume the $i$-th person to be born is numbered $i$.

Each query is one of the following three types:

1. 1 x: Ask what rank (in terms of smartness) the person numbered $x$ has in the whole family.
2. 2 x k: Ask for the number of the $k$-th smartest person among person $x$ and all their ancestors.
3. 3 x k: Ask for the number of the $k$-th smartest person among person $x$ and all their descendants.

Conan still has many cases to solve and does not want to waste time answering Ran’s questions. He hopes you can write a program to help him answer all queries.

Input Format

The first line contains two integers $n, q$, representing the number of people and the number of queries.

The second line contains $n - 1$ integers $f_{2 \dots n}$, where $f_i$ denotes the father of $i$.

The third line contains $n$ integers $a_{1 \dots n}$, where $a_i$ denotes the IQ value of $i$.

The next $q$ lines each contain two or three integers describing a valid query. The first integer is the query type, and the following one or two integers are the query parameters.

Output Format

Output $q$ lines, each containing one integer representing the answer to the query.

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

5
2
1
3
4
3
1
3
2
4
5

Hint

[Sample Explanation]

The formed tree is as follows:

First compare persons $2$ and $3$. Since person $3$ has the same IQ value as person $2$ and they have the same father, and person $3$ is born later than person $2$, condition 3 is satisfied, so person $3$ is smarter than person $2$.

Then compare persons $4$ and $5$. Since person $4$ has the same IQ value as person $5$ and they have different fathers, and person $4$’s father (person $3$) is smarter than person $5$’s father (person $2$), condition 2 is satisfied, so person $4$ is smarter than person $5$.

Then compare persons $1$ and $5$. Since person $5$ has the same IQ value as person $1$ and person $1$ has no father, and person $5$ is born later than person $1$, condition 3 is satisfied, so person $5$ is smarter than person $1$.

Then, using condition 1 to compare persons $2$ and $4$, we can sort the smartness of the $5$ people as: $3 > 2 > 4 > 5 > 1$.

[Constraints]

There are $10$ test points in total.

For the first $20\%$ of the data, $1 \le n, q \le 10 ^ 3$. Each test point is worth $7$ points, time limit 1 s.

For another $20\%$ of the data, each person has at most one son. Each test point is worth $9$ points, time limit 4 s.

For another $20\%$ of the data, $1 \le n, q \le 10 ^ 5$. Each test point is worth $9$ points, time limit 1.5 s.

For another $20\%$ of the data, only the first type of query is guaranteed. Each test point is worth $12$ points, time limit 1.5 s.

For $100\%$ of the data, $1 \le n, q \le 5 \times 10 ^ 5$, $1 \le a_i \le 10 ^ 9$. Each test point is worth $13$ points, time limit 2.5 s.

Translated by ChatGPT 5