e-olymp
Competitions

Segment Tree - Multiple Update

Persistent Array

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

  • ai[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 ai[j] - print the j-th element in the i-th version.

    Input

    The size of array n (1 n 105) and n elements of array. Then goes the number of queries m (1 m 105) 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 109. The array elements are numbered with integers from 1 to n.

    Output

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

    Time limit 1 second
    Memory limit 128 MiB
    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