Competitions

# Segment Tree - Multiple Update

# Persistent Array

The array is given (its first, initial version). You must be able to answer two questions:

**a**=_{i}[j]**x**- create the new version from**i**-th one, where the**j**-th element equals to**x**, and other elements are the same like in**i**-th version.**get a**- print the_{i}[j]**j**-th element in the**i**-th version.

**Input**

The size of array **n** (**1 **≤ **n **≤ **10 ^{5}**) and

**n**elements of array. Then goes the number of queries

**m**(

**1**≤

**m**≤

**10**) and

^{5}**m**queries themselves. The format is given in the sample input. If we have already

**k**array versions, the new one gets the number

**k + 1**. All array elements (old and new) are integers from

**0**to

**10**. The array elements are numbered with integers from

^{9}**1**to

**n**.

**Output**

For each **get** query print the corresponding element of the array.

Input example #1

6 1 2 3 4 5 6 11 create 1 6 10 create 2 5 8 create 1 5 30 get 1 6 get 1 5 get 2 6 get 2 5 get 3 6 get 3 5 get 4 6 get 4 5

Output example #1

6 5 10 5 10 8 6 30