Marked Ancestor Query on a Tree

In the year 2016, after recently learning about trees, Jiayuan is very excited and wants to solve the following problem. Given a rooted tree with root (1), the tree supports two operations:

1. Marking Operation: Mark a node. (Initially, only node (1) is marked and all other nodes are unmarked. A node can be marked multiple times.)

2. Query Operation: For a given node (x), find its nearest marked ancestor (a node is considered to be its own ancestor).

Your task is to process a series of operations and answer each query accordingly.

inputFormat

The first line contains two integers (n) and (q) ((1 \leq n, q \leq 10^5)), representing the number of nodes and the number of operations. The second line contains (n-1) integers (p_2, p_3, \dots, p_n), where (p_i) is the parent of the (i)-th node ((1 \leq p_i < i)).

Each of the following (q) lines contains two integers (op) and (x). If (op = 0), perform a marking operation on node (x). If (op = 1), perform a query operation on node (x).

outputFormat

For each query operation (where (op = 1)), output on a separate line the nearest marked ancestor of node (x).

sample

5 5
1 1 2 2
1 3
0 3
1 3
1 5
0 2

1
3
1