Persistent Array Versioning

Given an array of length \(N\), you need to maintain its persistent versions while supporting the following operations:

1. Modify: For a given historical version of the array, change the value at a specified position.
2. Query: For a given historical version of the array, retrieve the value at a specified position.

After each operation, a new version of the array is created. The version number of an operation is its order number (starting from \(1\)), while version \(0\) is the initial state of the array.

For a query operation, a new version is created as an exact copy of the queried version.

inputFormat

The first line contains two integers \(N\) and \(Q\) representing the length of the initial array and the number of operations, respectively.

The second line contains \(N\) integers representing the initial array.

Each of the following \(Q\) lines describes an operation in one of the following formats:

• 1 v pos val — based on version \(v\), change the element at position \(pos\) (1-indexed) to \(val\).
• 2 v pos — based on version \(v\), query the element at position \(pos\) (1-indexed). This creates a new version identical to version \(v\).

outputFormat

For each query operation (type 2), output the retrieved value on a new line in the order they appear in the operations.

sample

5 5
1 2 3 4 5
1 0 3 10
2 1 3
1 2 1 7
2 0 4
2 3 1

10
4
7