% Problem author: Sergey Kopeliovich
% Original source: Харьковские сборы, февраль 2012

\begin{problem}{Persistant Array}{parray.in}{parray.out}{2 секунды}{256 мегабайт}{}

Дан массив (вернее, первая, начальная его версия).

Нужно уметь отвечать на два запроса:

$\circ$ $a_i[j] = x$ --- создать из $i$-й версии новую, в которой $j$-й элемент равен $x$, а остальные элементы такие же, как в $i$-й версии.

$\circ$ \t{get} $a_i[j]$ --- сказать, чему равен $j$-й элемент в $i$-й версии.

\InputFile

Количество чисел в массиве $N$ ($1 \le N \le 10^5$) и $N$ элементов массива.
Далее количество запросов $M$ ($1 \le M \le 10^5$) и $M$ запросов. Формат описания запросов можно посмотреть в примере.
Если уже существует $K$ версий, новая версия получает номер $K+1$.
И исходные, и новые элементы массива --- целые числа от $0$ до $10^9$. Элементы в массиве нумеруются числами от $1$ до $N$.

\OutputFile

На каждый запрос типа \t{get} вывести соответствующий элемент нужного массива.

\Example

\begin{example}
\exmp{
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
}{
6
5
10
5
10
8
6
30
}%
\end{example}

\end{problem}
