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_i[j] - print the 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^5) and 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^9. The array elements are numbered with integers from 1 to n.

Output

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

Examples