Marble Journey on a Directed Graph

You are given a directed graph with n nodes numbered from 1 to n. Each node has an outdegree of either \(0\) or \(1\). The graph is described by an array of n integers, where the \(i\)-th integer indicates the destination node of an edge starting from node \(i\), or \(0\) if there is no outgoing edge from that node.

You need to answer q queries of two types:

1. 1 X: Given a starting node \(X\), simulate the motion of a marble. The marble follows the outgoing edge from the current node until it reaches a node with no outgoing edge. Output the final node reached by the marble.
2. 2 X: Delete the outgoing edge from node \(X\) (it is guaranteed that node \(X\) currently has an outgoing edge).

Note: Once an edge is deleted via a type 2 query, it remains deleted for all subsequent queries.

inputFormat

The first line contains two integers \(n\) and \(q\) \( (1 \le n, q \le 10^5)\), representing the number of nodes and the number of queries.

The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\) where \(a_i\) is either 0 or an integer in the range \([1, n]\). If \(a_i = 0\), then node \(i\) has no outgoing edge; otherwise, there is a directed edge from node \(i\) to node \(a_i\).

The following \(q\) lines describe the queries. Each query is in one of the following two formats:

• 1 X: Output the terminal node of the marble starting from node \(X\).
• 2 X: Delete the outgoing edge from node \(X\). It is guaranteed that node \(X\) currently has an outgoing edge.

outputFormat

For each query of type 1, output the terminal node reached by the marble on a new line.

sample

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

3
3
2
2