Family Tree Intelligence Ranking

A family started with a single person and grew as each person had children over time. Now there are n persons in this family, and the n-th person is Conan. It is known that the family forms a tree with n nodes.

To make his fabricated family background more realistic, Conan assigns an IQ value to every family member. However, a person’s intelligence is not determined solely by his own IQ but also by his ancestors’ intelligence and his birth order.

Specifically, for any two distinct persons A and B, A is considered smarter than B if and only if one of the following conditions holds:

1. A's IQ is higher than B's IQ.
2. A and B have the same IQ, they have different fathers (i.e. different immediate ancestors) and A's father is smarter than B's father.
3. A and B have the same IQ and either share the same father or one of them has no father; in this case, the one who was born later (has a larger birth number) is considered smarter.

An immediate consequence is that no two persons in the family have the same level of intelligence.

Conan needs to answer q queries from Lan. For clarification, assume that the person born i-th is numbered i (1 ≤ i ≤ n).

Each query is one of the following three types:

• 1 x: Query the overall intelligence ranking of person x in the entire family (smarter means a smaller rank number, i.e. rank 1 is the smartest).
• 2 x k: Among person x and all of his ancestors, find the k-th smartest person and output his number.
• 3 x k: Among person x and all of his descendants, find the k-th smartest person and output his number.

Input Format:

inputFormat

The first line contains two integers n and q — the number of persons in the family and the number of queries.

The second line contains n integers, where the i-th integer is the IQ value of person i.

The third line contains n-1 integers. For each person i (with 2 ≤ i ≤ n), the (i-1)-th integer is the father (immediate ancestor) of person i. Person 1 has no father.

Then follow q lines, each describing a query in one of the following formats:

• 1 x
• 2 x k
• 3 x k

outputFormat

For each query, output the answer on a separate line.

sample

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

1
5
2
4
4

</p>